Question
Odd-Even Swap Puzzle
Aiden discovers a strange puzzle in an old, dusty book. The puzzle presents him with a string of digits, S, of length N, and challenges him to create the smallest possible number by rearranging the digits. However, there’s a twist: he can only swap two adjacent digits if one is even and the other is odd.
Can Aiden figure out the smallest number possible by following this unusual rule?
Input
The first line of input contains a single integer N.
The next line of input contains a string of digits.
Constraints
1 ≤ N ≤ 105
'0' ≤ S[i] ≤ '9'
The next line of input contains a string of digits.
Constraints
1 ≤ N ≤ 105
'0' ≤ S[i] ≤ '9'
Output
Print the lexicographically smallest string possible.
Example
Sample Input
4
0709
Sample Output
0079
Explanation
Index 2 and 3 can be swapped as 7(odd) and 0(even) are of different parity.
4
0709
Sample Output
0079
Explanation
Index 2 and 3 can be swapped as 7(odd) and 0(even) are of different parity.