Два числа a и b записаны в шестнадцатеричной системе счисления. Запись обоих имеет длину n. Вы можете сколько угодно раз менять две соседние цифры местами в любом из чисел. Какое максимальное значение может быть у результата применения побитовой операции XOR к получившимся после применения таких перестановок числам?
Эта операция определена над двоичным представлением чисел.
Определим операцию побитового исключающего «ИЛИ» (XOR). Пусть даны два целых неотрицательных двоичных числа x и y длины k (возможно с ведущими нулями): xk-1...x2x1x0 и yk-1...y2y1y0. Здесь xi это i-й бит числа x, а yi это i-й бит числа y. Пусть r = x XOR y - результат операции XOR над числами x и y. Тогда двоичной записью r будет rk-1...r2r1r0, где:
\(r_i = \begin{cases} 1, ~ \text{если} ~ x_i ~ \neq ~ y_i \\ 0, ~ \text{если} ~ x_i ~ = ~ y_i \end{cases}\)
Входные данные
В первой строке содержится одно целое число n (1 <= n <= 100000) - длина записи чисел. Во второй строке задана запись числа a. В третьей строке задана запись числа b.
Буквы A, B, C, D, E, F отвечают за цифры 10, 11, 12, 13, 14, 15 в шестнадцатеричной системе счисления соответсвенно. Записи могут содержать ведущие нули.
Выходные данные
В единственной строке вам необходимо вывести одно шестнадцатеричное число длины n, которое является ответом на вопрос из условия.
Примечание
В первом примере можно поменять две соседние цифры в первом числе, получится F0 XOR 0E = FE.
Во втором примере любая перестановка цифр не меняет a XOR b. Обратите внимание, что длина выводимого числа должна быть равна n, поэтому надо выводить лидирующие нули.
В третьем примере можно получить 101010 из a и 010100 из b.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2
0F
0E
|
FE
|
| 2 |
3
000
000
|
000
|
| 3 |
6
010110
011000
|
111110
|