Problem Description

The expressions we usually write are called infix expressions because they place the operator between two operands. In many cases, parentheses are essential to determine the order of operations. However, postfix expressions do not require parentheses.

Postfix notation: When writing expressions, the operator follows the two operands, thus eliminating the need for parentheses and handling precedence. This simplifies the computer's processing rules to: compute sequentially from left to right and replace the operands with the result.

For example, 8-(3+2*6)/5+4 can be written as: 8 3 2 6 * + 5 / - 4 +

The calculation steps are:

8 3 2 6 * + 5 / - 4 +
8 3 12 + 5 / - 4 +
8 15 5 / - 4 +
8 3 - 4 +
5 4 +
9

Write a program to perform this conversion. Ensure that each data in the output is separated by a space.

Input Format

A single line, which is an infix expression. The input symbols only include these basic symbols 0123456789+-*/^(), and formats like 2*-3 will not appear.

The basic digits in the expression are all single-digit, and forms like 12 will not appear.

Do not check for errors in the input string.

Output Format

Several lines of postfix expressions, where the $(i+1)$-th line has one less operator and one less operand than the $i$-th line. The last line contains only one number, which is the result of the calculation.

Sample Input and Output

Sample Input #1

8-(3+2*6)/5+4

Sample Output #1

8 3 2 6 * + 5 / - 4 + 
8 3 12 + 5 / - 4 + 
8 15 5 / - 4 + 
8 3 - 4 + 
5 4 + 
9

Sample Input #2

2^2^3

Sample Output #2

2 2 3 ^ ^
2 8 ^
256

Notes

The result of the operation may be negative, and / denotes integer division. Each intermediate step will not exceed $2^{31}$. The length of the string does not exceed 100.

Note that the exponentiation operator ^ is right-associative, i.e., 2 ^ 2 ^ 3 is 2 ^ (2 ^ 3), and the postfix expression is 2 2 3 ^ ^.

Other operations with the same precedence are left-associative, i.e., 4 / 2 / 2 * 2 is ((4 / 2) / 2) * 2, and the postfix expression is 4 2 / 2 / 2 *.

It is guaranteed that there will be no negative exponents in exponentiation calculations, so all intermediate results are integers.

见题面 Input 部分

见题面 Output 部分