Have you solved ONP problem? Especially using brainf**k? This problem will give you extra points if you can solve ONP using brainf**k. Note that this problem has larger constraints.

The task is: "Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,...,z. Assume that there is only one RPN form (no expressions like a*b*c)."

Input

t [the number of expressions ≤ 1000]

expression [length = See: "Other Info" part]

[other expressions]

Output

The expressions in RPN form, one per line.

Example

Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output:
abc*+
ab+zx+*
at+bac++cd+^*

Other Info

Input: I deliberately not tell the input length, constraints, distribution, etc. You can guess it from judge output for my BF program (BF Cell Used) ;-) And of course I generate it randomly (But I can't tell the distribution).

This problem is using a custom judge, so you can see the detail after you get AC/WA.

The judge output format is like this: ("Code Length (Valid Command only)")"Cell Used"("BF Command executed").

Click here to see my submission result for this problem.

I have two solutions for this problem:
1) ID 9658441 (optimized): Judge output for my BF code is: (471)4320(606116310) meaning that my Valid BF commands = 471 commands and My code using 4320 BF cell and 606116310 commands executed.
2) ID 9658572 (golfed): Judge output for my BF code is: (295)4320(888371635) meaning that my Valid BF commands = 295 commands and My code using 4320 BF cell and 888371635 commands executed.

You can click (AC/WA) status for more detail.

My code running time is 0.68s (optimized solution) and 1.47s (golfed solution) and both using 1.6M of memory.

The time limit is ~14× my BF program top speed.

See also: Another problem added by Tjandra Satria Gunawan