F. Минимальное XOR-ирование строки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано целое число $$$n$$$ и строка $$$s$$$, состоящая из $$$2^n$$$ строчных букв латинского алфавита. Обозначим символы строки $$$s$$$ как $$$s_0s_1s_2\cdots s_{2^n-1}$$$.

Строка $$$t$$$ длины $$$2^n$$$ (символы которой будем обозначать как $$$t_0t_1t_2\cdots t_{2^n-1}$$$) называется XOR-ированием строки $$$s$$$, если существует целое число $$$j$$$ ($$$0\le j \leq 2^n-1$$$) такое, что для всех $$$0 \leq i \leq 2^n-1$$$ выполняется $$$t_i = s_{i \oplus j}$$$ (здесь $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ).

Найдите лексикографически минимальное XOR-ирование строки $$$s$$$.

Строка $$$a$$$ лексикографически меньше строки $$$b$$$, если и только если выполняется один из следующих пунктов:

  • $$$a$$$ — префикс $$$b$$$, но $$$a \ne b$$$;
  • в первой позиции, где $$$a$$$ и $$$b$$$ различны, в строке $$$a$$$ находится буква, которая встречается в алфавите раньше, чем соответствующая буква в $$$b$$$.
Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 18$$$).

Вторая строка содержит строку $$$s$$$, состоящую из $$$2^n$$$ строчных букв латинского алфавита.

Выходные данные

Выведите одну строку, содержащую лексикографически минимальное XOR-ирование строки $$$s$$$.

Примеры
Входные данные
2
acba
Выходные данные
abca
Входные данные
3
bcbaaabb
Выходные данные
aabbbcba
Входные данные
4
bdbcbccdbdbaaccd
Выходные данные
abdbdccacbdbdccb
Входные данные
5
ccfcffccccccffcfcfccfffffcccccff
Выходные данные
cccccffffcccccffccfcffcccccfffff
Входные данные
1
zz
Выходные данные
zz
Примечание

В первом примере лексикографически минимальное XOR-ирование $$$t$$$ строки $$$s =$$$«acba» является «abca». Это XOR-ирование, так как для $$$j = 3$$$ получаем:

  • $$$t_0 = s_{0 \oplus j} = s_3 =$$$ «a»;
  • $$$t_1 = s_{1 \oplus j} = s_2 =$$$ «b»;
  • $$$t_2 = s_{2 \oplus j} = s_1 =$$$ «c»;
  • $$$t_3 = s_{3 \oplus j} = s_0 =$$$ «a».
Не существует XOR-ирования строки $$$s$$$ лексикографически меньше, чем «abca».

Во втором примере лексикографически минимальное XOR-ирование соответствует выбору числа $$$j = 4$$$ из определения XOR-ирования.

В третьем примере лексикографически минимальное XOR-ирование соответствует выбору числа $$$j = 11$$$ из определения XOR-ирования.

В четвертом примере лексикографически минимальное XOR-ирование соответствует выбору числа $$$j = 10$$$ из определения XOR-ирования.

В пятом примере лексикографически минимальное XOR-ирование соответствует выбору числа $$$j = 0$$$ или числа $$$j = 1$$$ из определения XOR-ирования.