Два числа $$$a$$$ и $$$b$$$ записаны в шестнадцатеричной системе счисления. Запись обоих имеет длину $$$n$$$. Вы можете сколько угодно раз менять две соседние цифры местами в любом из чисел. Какое максимальное значение может быть у результата применения побитовой операции XOR к получившимся после применения таких перестановок числам?
Эта операция определена над двоичным представлением чисел.
Определим операцию побитового исключающего «ИЛИ» (XOR). Пусть даны два целых неотрицательных двоичных числа $$$x$$$ и $$$y$$$ длины $$$k$$$ (возможно с ведущими нулями): $$$x_{k-1} \dots x_2 x_1 x_0$$$ и $$$y_{k-1} \dots y_2 y_1 y_0$$$. Здесь $$$x_i$$$ это $$$i$$$-й бит числа $$$x$$$, а $$$y_i$$$ это $$$i$$$-й бит числа $$$y$$$. Пусть $$$r = x ~ \text{XOR} ~ y$$$ — результат операции XOR над числами $$$x$$$ и $$$y$$$. Тогда двоичной записью $$$r$$$ будет $$$r_{k-1} \dots r_2 r_1 r_0$$$, где: $$$$$$ r_i = \begin{cases} 1, ~ \text{если} ~ x_i ~ \neq ~ y_i \\ 0, ~ \text{если} ~ x_i ~ = ~ y_i \end{cases} $$$$$$
В первой строке содержится одно целое число $$$n$$$ ($$$1 \leq n \leq 100\,000$$$) — длина записи чисел. Во второй строке задана запись числа $$$a$$$. В третьей строке задана запись числа $$$b$$$.
Буквы $$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$, $$$E$$$, $$$F$$$ отвечают за цифры $$$10$$$, $$$11$$$, $$$12$$$, $$$13$$$, $$$14$$$, $$$15$$$ в шестнадцатеричной системе счисления соответсвенно. Записи могут содержать ведущие нули.
В единственной строке вам необходимо вывести одно шестнадцатеричное число длины $$$n$$$, которое является ответом на вопрос из условия.
2 0F 0E
FE
3 000 000
000
6 010110 011000
111110
В первом примере можно поменять две соседние цифры в первом числе, получится F0 XOR 0E = FE.
Во втором примере любая перестановка цифр не меняет $$$a \ \ \text{XOR} \ \ b$$$. Обратите внимание, что длина выводимого числа должна быть равна $$$n$$$, поэтому надо выводить лидирующие нули.
В третьем примере можно получить $$$101010$$$ из $$$a$$$ и $$$010100$$$ из $$$b$$$.
В данной задаче $$$50$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$2$$$ балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при $$$1 \leq n \leq 8$$$, наберут не менее $$$10$$$ баллов.
Решения, корректно работающие при $$$a$$$, состоящем только из цифры $$$0$$$, наберут не менее $$$10$$$ баллов.
Решения, корректно работающие, когда $$$a$$$ и $$$b$$$ состоят только из цифр $$$0$$$ и $$$1$$$, наберут не менее $$$10$$$ баллов.
Решения, корректно работающие, когда $$$a$$$ состоит только из цифр $$$0$$$, $$$1$$$, $$$2$$$, $$$3$$$, а $$$b$$$ состоит только из цифр $$$0$$$, $$$4$$$, $$$8$$$, $$$C$$$, наберут не менее $$$10$$$ баллов.
Решения, корректно работающие, когда $$$a$$$ состоит из не более двух различных цифр и $$$b$$$ состоит из не более двух различных цифр, наберут не менее $$$30$$$ баллов.