십육진수 혼란

ChatGPT가 생성한 원본 이미지를 편집함 (©OpenAI, 허가를 받아 사용)

Addison Hex은 다음 두뇌 올림픽을 위해 훈련 중인 유망한 선수이다. Addison이 출전하고 싶은 종목은 Fast Hexadecimal Addition이지만, 상위 16명만 결승에 진출한다. 이는 지금부터 많은 연습이 필요하다는 뜻이다!

고속 십육진수 덧셈에서는 참가자들에게 각각 최대 4자리인 십육진수의 수열을 매우 빠르게 보여 주며, 참가자들은 마지막에 이 수들의 합을 십육진수로 정확히 답해야 한다. 어떤 수에도 선행하는 영이 없으며, 정수 0은 정확히 하나의 0으로 표현된다.

Addison은 후원 계약이 전혀 없어서, 수들을 빠르게 깜박여 보여 주는 오래된 LCD 디스플레이로 덧셈을 연습해야 한다. 안타깝게도 표준 7-세그먼트 디스플레이에서는 숫자 8과 B가 똑같이 보인다. 또한 숫자 0과 D도 똑같이 보인다. 다행히 그 밖의 모든 숫자는 명확하게 구별된다. 정확한 합을 구하는 대신, 그녀는 자신이 본 것을 바탕으로 가능한 최댓값의 합과 가능한 최솟값의 합을 모두 구하는 연습을 한다. Addison은 수들을 최대한 빠르게 기록하려다 선행하는 영이 있는 수를 볼 수도 있지만, 원래 수에는 선행하는 영이 없다는 사실도 알고 있으며 계산할 때 이를 고려한다.

다시 말해, 십육진수의 숫자 A', B', ..., `F'은 각각 10, 11, ..., 15에 해당하는 십진수 값을 갖는다.

첫 번째 줄에 Addison이 보는 정수의 개수를 나타내는 양의 정수 $N$ ($1 \leq N \leq 1\,000$)이 주어진다. 이어지는 $N$개의 각 줄에는 최대 4자리인 음이 아닌 십육진수 정수가 주어진다. 각 자릿값은 십진 숫자 또는 대문자 A', B', C', D', E', F' 중 하나이다. 각 수는 Addison이 본 모습대로 기록된다.

첫 번째 줄에 가능한 최댓값의 합을 십육진수로 출력한다. 두 번째 줄에 가능한 최솟값의 합을 십육진수로 출력한다. 출력에는 선행하는 영이 없어야 하며, 정수 0은 정확히 하나의 0으로 표현해야 한다.