P1018 Extreme Trees 1 - The Order of the Binary Tree 1

Difficulty: \(\color{grey}250\)

Problem Statement

We have a binary tree.

Now you are told the preorder or the postorder of the tree, please find out the root of the binary tree.

Input

\(C\ S\)

Here \(C\) is the sort of the order, which will be "pre" if it is preorder, "post" if it is postorder. \(S\) is the sequence of the order.

Output

\(R\)

Here \(R\) is the root of the binary tree.

Constraints

• \(C =\) pre or post.
• \(S\) is made of uppercase letters, and \(1 \le |S| \le 100\).
• It is guaranteed there is only one root on the tree(OBVIOUSLY), so \(R\) should be only one letter.

Samples

Input 1

pre
ABCDEFGHIJKLMNOPS

Output 1

A

Input 2

post
ABCDEFHIJKLMNOPQRSTUVWXYZ

Output 2

Z