Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

data structures

divide and conquer

greedy

hashing

sortings

strings

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Minimal String Xoration

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou 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".

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/28/2024 19:52:34 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|