F. Minimal String Xoration
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$ and a string $$$s$$$ consisting of $$$2^n$$$ lowercase letters of the English alphabet. The characters of the string $$$s$$$ are $$$s_0s_1s_2\cdots s_{2^n-1}$$$.

A string $$$t$$$ of length $$$2^n$$$ (whose characters are denoted by $$$t_0t_1t_2\cdots t_{2^n-1}$$$) is a xoration of $$$s$$$ if there exists an integer $$$j$$$ ($$$0\le j \leq 2^n-1$$$) such that, for each $$$0 \leq i \leq 2^n-1$$$, $$$t_i = s_{i \oplus j}$$$ (where $$$\oplus$$$ denotes the operation bitwise XOR).

Find the lexicographically minimal xoration of $$$s$$$.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

  • $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
  • in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.
Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 18$$$).

The second line contains a string $$$s$$$ consisting of $$$2^n$$$ lowercase letters of the English alphabet.

Output

Print a single line containing the lexicographically minimal xoration of $$$s$$$.

Examples
Input
2
acba
Output
abca
Input
3
bcbaaabb
Output
aabbbcba
Input
4
bdbcbccdbdbaaccd
Output
abdbdccacbdbdccb
Input
5
ccfcffccccccffcfcfccfffffcccccff
Output
cccccffffcccccffccfcffcccccfffff
Input
1
zz
Output
zz
Note

In the first test, the lexicographically minimal xoration $$$t$$$ of $$$s =$$$"acba" is "abca". It's a xoration because, for $$$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".
There isn't any xoration of $$$s$$$ lexicographically smaller than "abca".

In the second test, the minimal string xoration corresponds to choosing $$$j = 4$$$ in the definition of xoration.

In the third test, the minimal string xoration corresponds to choosing $$$j = 11$$$ in the definition of xoration.

In the fourth test, the minimal string xoration corresponds to choosing $$$j = 10$$$ in the definition of xoration.

In the fifth test, the minimal string xoration corresponds to choosing either $$$j = 0$$$ or $$$j = 1$$$ in the definition of xoration.