Description

平常我们书写的表达式称为中缀表达式，因为它将运算符放在两个操作数中间，许多情况下为了确定运算顺序，括号是不可少的，而后缀表达式就不必用括号了。

后缀标记法：书写表达式时采用运算紧跟在两个操作数之后，从而实现了无括号处理和优先级处理，使计算机的处理规则简化为：从左到右顺序完成计算，并用结果取而代之。

例如：$8-(3+2*6)/5+4$可以写为：$8$ $3$ $2$ $6$ $* + 5 / – 4 +$

其计算步骤为：

$8$ $3$ $2$ $6$ $* + 5 / - 4 +$

$8$ $3$ $12$ $+ 5 / - 4 +$

$8$ $15$ $5$ $/ - 4 +$

$8$ $3$ $- 4 +$

$5$ $4$ $+$

$9$

编写一个程序，完成这个转换，要求输出的每一个数据间都留一个空格。

Format

Input

就一行，是一个后缀表达式。输入的符号中只有这些基本符号“$0123456789+-*/^()$”，并且不会出现形如2*-3的格式。

表达式中的基本数字也都是一位的，不会出现形如$12$形式的数字。

所输入的字符串不要判错。

Output

若干个中缀表达式，第$I+1$行比第I行少一个运算符和一个操作数，数据项之间用空格分隔，最后一行只有一个数字，表示运算结果。

运算的结果可能为负数，“$/$”以整除运算。并且中间每一步绝对值都小于2^31^。

Samples

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

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

Limitation

1s, 1024KiB for each test case.