该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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