给定一个整数 $$$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$$$ 的异解,如果存在整数 $$$j$$$ ($$$0\le j \leq 2^n-1$$$),例如对于每个 $$$0 \leq i \leq 2^n-1$$$,$$$t_i = s_{i \oplus j}$$$ (其中 $$$\oplus$$$ 表示按位异或运算)。
求 $$$s$$$ 按字典顺序排列的最小 xoration。
当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:
- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中的某个字母比 $$$b$$$ 中的相应字母更早出现。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 18$$$)。
第二行包含一个字符串$$$s$$$,由$$$2^n$$$英文字母的小写字母组成。
输出
打印一行,其中包含 $$$s$$$ 的字典顺序最小排序。
示例
输入 #1
2 acba
输出 #1
abca
输入 #2
3 bcbaaabb
输出 #2
aabbbcba
输入 #3
4 bdbcbccdbdbaaccd
输出 #3
abdbdccacbdbdccb
输入#4
5 ccfcffccccccffcfcfccfffffcccccff
输出#4
cccccffffcccccffccfcffcccccfffff
输入 #5
1 zz
输出 #5
zz
注意
在第一个测试中,$$$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”。
在第二个测试中,最小字符串 xoration 对应于在 xoration 的定义中选择 $$$j = 4$$$。
在第三个测试中,最小字符串 xoration 对应于在 xoration 的定义中选择 $$$j = 11$$$。
在第四个测试中,最小字符串 xoration 对应于在 xoration 的定义中选择 $$$j = 10$$$。
在第五个测试中,最小字符串 xoration 对应于在 xoration 的定义中选择 $$$j = 0$$$ 或 $$$j = 1$$$。