CF1654F.Minimal String Xoration

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

给定一个整数 $n$ 和一个由 $2^n$ 个小写英文字母组成的字符串 $s$。字符串 $s$ 的字符表示为 $s_0s_1s_2\cdots s_{2^n-1}$。

长度为 $2^n$ 的字符串 $t$（其字符表示为 $t_0t_1t_2\cdots t_{2^n-1}$）被称为 $s$ 的一个异或变换（xoration），当且仅当存在一个整数 $j$（满足 $0 \le j \leq 2^n-1$），使得对每个 $0 \leq i \leq 2^n-1$，均有 $t_i = s_{i \oplus j}$（其中 $\oplus$ 表示按位异或运算）。

请找出 $s$ 的字典序最小的异或变换。

字符串 $a$ 字典序小于字符串 $b$，当且仅当满足以下条件之一：

• $a$ 是 $b$ 的真前缀（即 $a$ 是 $b$ 的前缀且 $a \ne b$）；
• 在 $a$ 与 $b$ 首次出现不同字符的位置上，$a$ 中该位置的字母在字母表中早于 $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.

第一行包含一个整数 $n$（$1 \le n \le 18$）。

第二行包含一个字符串 $s$，由 $2^n$ 个小写英文字母组成。

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

输出一行，包含字符串 $s$ 的字典序最小的异或变换结果。

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.

在第一个测试中，字符串 $s =$ "acba" 的字典序最小异或变换 $t$ 为 "abca"。它是一个异或变换，因为当 $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"。

不存在字典序比 "abca" 更小的 $s$ 的异或变换。

在第二个测试中，字典序最小的字符串异或变换对应于异或变换定义中选择 $j = 4$。

在第三个测试中，字典序最小的字符串异或变换对应于异或变换定义中选择 $j = 11$。

在第四个测试中，字典序最小的字符串异或变换对应于异或变换定义中选择 $j = 10$。

在第五个测试中，字典序最小的字符串异或变换对应于异或变换定义中选择 $j = 0$ 或 $j = 1$。