Problem A
Calculator with Postfix Notation, Infix to Postfix Conversion

You are tasked with implementing a calculator that uses postfix notation in its internal representation. Postfix notation is a way of writing expressions that makes them more efficient for computers to evaluate compared to the standard infix notation that you have used in mathematics so far.

This calculator handles arithmetic expressions consisting of a limited set of symbols: positive integers, the operators $\texttt{+}, \texttt{-}, \texttt{*}, \texttt{/}$, and left and right parentheses.

In standard infix notation, operators are placed between operands, and parentheses are used to clarify the order of operations. As usual, $\texttt{*}$ and $\texttt{/}$ have higher precedence than $\texttt{+}$ and $\texttt{-}$, parentheses indicate that expressions within them should be evaluated first, and if there are multiple operators with the same precedence, the operations are performed from left to right.

In postfix notation, operators are placed after the operands. Parentheses are unnecessary because the order of operations is determined by the notation itself. Postfix expressions are evaluated by processing operands and operators from left to right. When an operator is encountered, it is applied to the most recently encountered operands.

Here are some examples of expressions in infix and their corresponding postfix forms:

• "2 + 3" $\ \ \rightarrow \ \ $ "2 3 +"

• "14 * ( 2 + 3 )" $\ \ \rightarrow \ \ $ "14 2 3 + *"

• "( ( 3 + 5 * 1 ) / 8) * 14 " $\ \ \rightarrow \ \ $ "3 5 1 * + 8 / 14 *"

Input

The input consists of a single line, which is an infix expression $U_1 \ldots U_N$, where $U_i$ is either an operand (a positive integer), an operator ($\texttt{+}$, $\texttt{-}$, $\texttt{*}$, or $\texttt{/}$), or a parenthesis (left or right).

The infix expression is space-separated between all $U_i$, and it is guaranteed that the total number of operands, operators, and parentheses is less than $5000$ (i.e., $N < 5000$). If $U_i$ is an integer, it is also guaranteed that $0 \leq U_i \leq 1000$.

In this problem, it is guaranteed that the infix expression is valid.

Output

Print the given expression in its postfix form, with spaces between all operands and operators.

Explanation of Sample 1

The postfix form of "2 + 3" is "2 3 +". Note, however, that the postfix form "3 2 +" produces the same result as the given infix expression, but the numbers in the expression should be written in the same order as given in the infix form. Therefore, "3 2 +" is not the correct answer.

2 + 3

2 3 +

4 * 3 - 2

4 3 * 2 -

( 3 + 4 ) / 7 + ( 8 / 4 - 9 / 3 )

3 4 + 7 / 8 4 / 9 3 / - +

( ( ( 120 / 5 + 6 ) / 10 * 5 ) + 36 - 1 ) / 25

120 5 / 6 + 10 / 5 * 36 + 1 - 25 /

( ( 3 + 5 * 1 ) / 8 ) * 14

3 5 1 * + 8 / 14 *