给定一个合法的中缀表达式，请将其转换为对应的逆波兰表达式（后缀表达式）。

表达式中只包含：

• 非负整数
• 二元运算符 +、-、*、/
• 左右括号 (、)

同一优先级的运算符按从左到右的顺序计算。

输出转换后的逆波兰表达式，各个数字和运算符之间用一个空格分隔。

输入格式

输入一行，一个合法的中缀表达式 $S(1 \leq |S| \leq 10^5)$。

保证表达式中不含空格，且所有整数均为十进制非负整数且 $\leq 10^9$。

输出格式

输出一行，表示对应的逆波兰表达式。

要求每个数字或运算符之间恰好用一个空格分隔。

样例输入

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

样例输出

3 5 + 2 4 - * 6 3 / +