Description

We can classify strings composed of "0" and "1" into three categories: strings consisting entirely of "0" are called B strings, strings consisting entirely of "1" are called I strings, and strings containing both "0" and "1" are called F strings.

An FBI tree is a binary tree[1] whose node types also include F nodes, B nodes, and I nodes. A binary string S of length 2^N can be used to construct an FBI tree T recursively as follows:

1) The root node of T is R, and its type is the same as the type of the string S;

2) If the length of the string S is greater than 1, split the string S from the middle into two equal-length substrings S1 and S2; construct the left subtree T1 of R using the left substring S1, and construct the right subtree T2 of R using the right substring S2.

Now, given a binary string of length 2^N, please use the above method to construct an FBI tree and output its post-order traversal[2] sequence.

[1] Binary tree: A binary tree is a finite set of nodes, which is either empty or consists of a root node and two disjoint binary trees. These two disjoint binary trees are called the left subtree and right subtree of the root node, respectively.

[2] Post-order traversal: Post-order traversal is a method of depth-first traversal of a binary tree. Its recursive definition is: first traverse the left subtree in post-order, then traverse the right subtree in post-order, and finally visit the root.

Input Format

The first line of input is an integer N (0 ≤ N ≤ 10). The second line is a binary string of length 2^N.

Output Format

The output consists of a single line containing a string, which is the post-order traversal sequence of the constructed FBI tree.

```input1 3 10001011 ``` ```output1 IBFBBBFIBFIIIFF ``` ## Hint

For 40% of the data, N ≤ 2;

For all data, N ≤ 10.

Source

CodesOnline