FBI Tree Postorder Traversal

Given a binary string S of length \(2^N\) composed of characters '0' and '1', we first classify any binary string into three types:

• B string: a string that contains only 0's.
• I string: a string that contains only 1's.
• F string: a string that contains both 0 and 1.

An FBI tree is a full binary tree whose nodes are also of three types: F, B, and I. The tree is constructed recursively from the given binary string S as follows:

1. The root node R is assigned the type of S. That is, if S consists of only 0's then R is of type B; if only 1's then I; otherwise F.
2. If the length of S is greater than 1, split S into two equal halves \(S_1\) and \(S_2\) (i.e. each of length \(2^{N-1}\)). Recursively construct the left subtree using \(S_1\) and the right subtree using \(S_2\), then attach them to R.

Your task is to construct the FBI tree using the above method and output its postorder traversal sequence. In the postorder traversal, you should first visit the left subtree, then the right subtree, and finally the current node.

Note: Use LaTeX format (e.g. \(2^N\)) for all formulas.

inputFormat

The input consists of a single line containing a binary string S. The length of S is \(2^N\) for some positive integer N.

outputFormat

Output a single line representing the postorder traversal sequence of the constructed FBI tree. Each character in the output is the type of the node ('B', 'I' or 'F').

sample

0

B