Description

In this lab, you are tasked with converting a postfix expression (also known as Reverse Polish Notation) into its equivalent prefix expression (Polish Notation).

This conversion must be performed by first constructing an expression tree from the postfix string and then traversing the tree to generate the prefix string. The algorithm is as follows:

1. Construct the Expression Tree: You will use a stack to build the tree. Read the postfix expression from left to right, token by token.

   • If the token is an operand (a variable), create a new single-node tree and push it onto the stack.
   • If the token is an operator, pop two trees from the stack. The first tree popped is the right child ($T_2$), and the second is the left child ($T_1$). Create a new tree whose root is the operator and whose children are $T_1$ and $T_2$. Push this new composite tree back onto the stack.

2. Generate the Prefix Expression: After iterating through all tokens, the stack will contain one final tree. Perform a preorder traversal (Root, Left, Right) on this tree. The sequence of visited nodes forms the final prefix expression.

For example, for the postfix expression A B + C *, the final tree would look like this:

      *
     / \
    +   C
   / \
  A   B

A preorder traversal of this tree results in the prefix expression: * + A B C.

Format

Input

• The first line contains a single integer $N$ ($1 \leq N \leq 100$), representing the number of tokens in the expression.
• The second line contains the postfix expression, consisting of $N$ tokens.
  • Operands are single uppercase letters (A-Z).
  • Operators are the four binary operators: +, -, *, /.
  • Each token is separated from the next by a single space.

Output

• A single line containing the corresponding prefix expression, with each token separated by a single space.

Samples

9
A B + C *

* + A B C

13
A B C * + D /

/ + A * B C D

13
A B + C D - *

* + A B - C D

Limitation

1s, 128MiB for each test case.