201302: [AtCoder]ARC130 C - Digit Sum Minimization

Problem Statement

Given are positive integers $a, b$, where none of the digits is $0$.

Permute the digits of each of $a$ and $b$ so that the sum of the digits in $a+b$ is minimized.

Constraints

• $1\leq a, b< 10^{100000}$
• None of the digits of $a$ and $b$ is $0$.

Input

Input is given from Standard Input in the following format:

$a$
$b$

Output

After permuting the digits of each of $a$ and $b$ so that the sum of the digits in $a+b$ is minimized, print $a$ in the first line and $b$ in the second line.

If multiple solutions exist, printing any of them will be accepted.

Sample Input 1

253
286

Sample Output 1

532
268

We have $532 + 268 = 800$, whole digits sum to $8+0+0=8$.

Other solutions will also be accepted, such as $(a, b) = (325, 682)$.

Sample Input 2

345
556

Sample Output 2

435
565

We have $435+565=1000$, whole digits sum to $1+0+0+0=1$.

Sample Input 3

123
987987

Sample Output 3

312
799788

We have $312 + 799788 = 800100$, whole digits sum to $8+0+0+1+0+0=9$.

Sample Input 4

11111111111111111111
111111111111111111111111111111

Sample Output 4

11111111111111111111
111111111111111111111111111111