Description
Domo is a brilliant dog. When he gets enough sleep, he will be happy.
Unfortunately, he got some problems with his homework this evening. He mistakes 'postfix' as 'prefix', which makes him can't go to sleep until he corrects his homework.
Given a prefix expression, please convert it to the postfix expression or Domo will be punished since he didn't finish his homework.
Prefix: The operator appears in the expression before the operands. Simply of the form (operator operand1 operand2).
Postfix: The operator appears in the expression after the operands. Simply of the form (operand1 operand2 operator).
Take an Example: (A+B) * (C-D)
Prefix: * + A B - C D
Postfix: A B + C D - *
This problem is testing your recursion skill, so don't consider if the expression is valid or not (such as divided by zero)
Input
The first line contains a prefix expression, in which each element is separated with a blank.
It's guaranteed that the number of elements will not exceed 500.
Output
Print the corresponding postfix expression from the given prefix expression, and separate each element with a blank.
You don't need to print a newline character in this problem, I apologize for any inconvenience.
Remember to print a newline character at the end of each line.