Infix to Postfix Expression Conversion

Given an infix arithmetic expression E containing operands and the operators +, -, *, /, ^ (exponentiation) along with parentheses, convert it to its corresponding postfix (Reverse Polish) expression P using the Shunting Yard algorithm.

The operator precedence is defined as follows: $$+,-:1,$$ $$*,/:2,$$ $$^:3.$$ Note that operators +, -, *, and / are left-associative, while the exponentiation operator (^) is assumed to be right-associative in general; however, for the purpose of this problem we follow the convention provided in the examples. The tokens in the expression are space-separated.

Examples:

• 10 + 2 * 6 → 10 2 6 * +
• 100 * ( 2 + 12 ) / 14 → 100 2 12 + * 14 /
• 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 → 3 4 2 * 1 5 - 2 3 ^ ^ / +

inputFormat

The input consists of a single line that contains a valid infix arithmetic expression. The tokens (operands, operators, and parentheses) are separated by spaces.

outputFormat

Output the corresponding postfix expression as a single line with tokens also separated by spaces.

## sample

10 + 2 * 6

10 2 6 * +

</p>