codeforces#P1654F. Minimal String Xoration

    ID: 32782 远端评测题 3000ms 512MiB 尝试: 0 已通过: 0 难度: 10 上传者: 标签>bitmasksdata structuresdivide and conquergreedysortingsstrings*2800

Minimal String Xoration

Description

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$.

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.

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

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$.

Samples

2
acba
abca
3
bcbaaabb
aabbbcba
4
bdbcbccdbdbaaccd
abdbdccacbdbdccb
5
ccfcffccccccffcfcfccfffffcccccff
cccccffffcccccffccfcffcccccfffff
1
zz
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.