Addison Hex 是一名有抱负的选手，正在为下一届脑力奥林匹克运动会进行训练。Addison 想要参加的项目是“快速十六进制加法”，但只有前 16 名才能晋级决赛。这意味着从现在开始必须进行大量的练习！

图像修改自 ChatGPT 生成的原图（©OpenAI，经授权使用）

在快速十六进制加法中，参赛者会非常快速地看到一系列十六进制数（每个数最多 4 位），他们必须在最后正确地给出这些数的十六进制和。原始数字中不会有前导零，且整数 0 将仅由一个 0 表示。

Addison 没有任何赞助，所以她只能使用一个老旧的 LCD 显示屏，该屏幕会快速闪烁数字供她相加。不幸的是，在标准的七段数码管显示中，数字 8 和 B 看起来是一样的。此外，数字 0 和 D 看起来也是一样的。值得庆幸的是，所有其他数字都是清晰无歧义的。由于无法确定确切的和，她决定通过根据自己所看到的数字找出可能的最大和与最小和来进行练习。虽然 Addison 在尽力快速记录数字时可能会看到带有前导零的数字，但她也知道原始数字是没有前导零的，并在计算中会考虑到这一点。

友情提示，十六进制中的数字 'A'、'B'、……、'F' 分别对应十进制中的 10、11、……、15。

输入格式

第一行包含一个正整数 $N$（$1 \le N \le 1\,000$），表示 Addison 看到的整数个数。

接下来的 $N$ 行，每行包含一个十六进制的非负整数，最多 4 位。每个数位是十进制数字或大写字母 'A'、'B'、'C'、'D'、'E'、'F' 之一。每个数字都是根据 Addison 所看到的内容记录下来的。

输出格式

第一行输出可能的最大十六进制和。

第二行输出可能的最小十六进制和。

输出中不应有前导零，且整数 0 应仅由一个 0 表示。

样例

输入样例 1

2
ABCD
1038

输出样例 1

C908
B8F8

输入样例 2

10
1111
2222
3333
4444
5555
6666
7777
9999
1234
2345

输出样例 2

2ACEE
2ACEE

输入样例 3

10
1234
8008
6348
2008
ABCD
EFAB
2147
3728
30DB
BDBD

输出样例 3

450B7
3B6EB

输入样例 4

4
0012
D012
ABCD
0

输出样例 4

265FE
248E4