Problem H
Hexadecimal Confusion
Addison Hex is an aspiring athlete training for the next mental Olympics. The event Addison wants to compete in is Fast Hexadecimal Addition, but only the top 16 people will make it to the finals. That means a lot of practice from now on!
In Fast Hexadecimal Addition, contestants are shown very quickly a sequence of hexadecimal numbers (up to 4 digits each) and they must correctly give the sum of these numbers at the end in hexadecimal. No numbers will have leading zeros, and the integer 0 will be represented by exactly one 0.
Addison does not have any sponsorship deals, so she is stuck with an old LCD display that will flash the numbers quickly for her to add. Unfortunately, in the standard 7-segment displays, the digits 8 and B look the same. Also, the digits 0 and D look the same. Thankfully all other digits are unambiguous. Instead of finding the exact sum, she will practice by finding both the maximum possible sum and the minimum possible sum based on what she sees. While Addison may see numbers with leading zeros as she tries to record the numbers as quickly as she can, she also knows that the original numbers have no leading zeros and will take that into account in her calculations.
As a reminder, the digits ‘A’, ‘B’, …, ‘F’ in hexadecimal have equivalent decimal values of 10, 11, …, 15, respectively.
Input
The first line contains a positive integer $N$ ($1 \leq N \leq 1\, 000$), which is the number of integers that Addison sees. Each of the next $N$ lines contains a nonnegative integer in hexadecimal, with up to 4 digits. Each digit is one of the decimal digits or an uppercase letter ‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’. Each number is recorded based on what Addison sees.
Output
On the first line, output the maximum possible sum in hexadecimal. On the second line, output the minimum possible sum in hexadecimal. There should be no leading zeros in the output, and the integer 0 should be represented by exactly one 0.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 ABCD 1038 |
C908 B8F8 |
| Sample Input 2 | Sample Output 2 |
|---|---|
10 1111 2222 3333 4444 5555 6666 7777 9999 1234 2345 |
2ACEE 2ACEE |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 1234 8008 6348 2008 ABCD EFAB 2147 3728 30DB BDBD |
450B7 3B6EB |
| Sample Input 4 | Sample Output 4 |
|---|---|
4 0012 D012 ABCD 0 |
265FE 248E4 |
