You are given the sequence in which the nodes are entered in the Binary Search Tree. Print the preorder or postorder traversal depending upon the inputs.

Input

First line contains 'n', number of nodes. Next line contains n elements. Next line contains a string "pre" or "post" (quotes for clarity).

Output

Print the preorder traversal or postorder traversal in one line.

Example

Input:
9
10 7 15 9 12 17 8 11 13
pre

Output:
10 7 9 8 15 12 11 13 17