Два числа a и b записаны в двоичной системе счисления. Запись обоих имеет длину 2n. Обе записи разбиты на n блоков по 2 стоящие рядом цифры. В каждом из чисел вы можете сколько угодно раз менять два произвольных блока местами. Какое максимальное значение может быть у результата применения побитовой операции 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.
Для удобства блоки разделены символом «|».
Выходные данные
В единственной строке вам необходимо вывести одно двоичное число из n блоков, которое является ответом на задачу, в таком же блочном формате, в каком заданы числа a и b.
Примечание
В первом примере можно поменять два соседних блока в первом числе, получится 11|00 XOR 00|10=11|10.
Во втором примере любая перестановка цифр не меняет a XOR b. Обратите внимание, что длина выводимого числа должна состоять из n блоков, поэтому надо выводить блоки из лидирующих нулей.
В третьем примере можно получить 101001 из a и 010100 из b.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2
00|11
00|10
|
11|10
|
| 2 |
3
00|00|00
00|00|00
|
00|00|00
|
| 3 |
3
10|10|01
00|01|01
|
11|11|01
|