ACM-ICPC Indonesia National Contest 2010

Problem C

Stack Machine Simulator

Time Limit: 2s

A stack machine has two type of operations:

For example, command string "+a+b+c+d^" means: push a, push b, push c, push d and reverse. After "+a+b+c+d^" executed, the stack contains "dcba". Write a program which take the command string as the input and output the stack's content after the command is executed.


Input

The first line of input contains an integer T (1 ≤ T ≤ 1,000) the number of cases. Each case contains a string S denoting the command string as described above. S will be between 1 and 100 characters long.

Output

For each test case, output in a line the content of the stack after the command is executed.



Sample InputOutput for Sample Input
2
+a+b
+A+B^+c^
ab
cAB