Zadanie

Jeden zásadný rozdiel

Počet bodov: 60

Pred pár týždňami sa dokončil v štátnej správe projekt za trinásťcifernú sumu (v mikrocentoch).

Bol to program, ktorý dostal na vstupe matematický výraz v tzv. postfixovej notácii a vyrátal jeho výsledok.

Postfixová notácia funguje tak, že namiesto toho, aby sme operátory písali medzi operandami, píšeme ich za nimi. Napríklad (x+y)*z zapíšeme ako xy+z*.

V takejto notácii sa výraz ľahko vyhodnocuje programom. Stačí začať s prázdnym zásobníkom a čítať výraz zľava doprava. Keď prečítame operand, pridáme ho na vrch zásobníka. Keď prečítame nejaký operátor O, zoberieme dve vrchné hodnoty zo zásobníka, aplikujeme na ne operátor a výsledok vrátime do zásobníka. V pseudokóde by to teda vyzeralo takto:

a = zasobnik.pop()
b = zasobnik.pop()
zasobnik.push(b O a)

Na konci procesu bude jediná hodnota v zásobníku výsledok celého výrazu. Môžete si overiť, že tento postup vyráta z výrazu xy+z* hodnotu (x+y)*z.

V implementácii programu v štátnej správe je však jeden zásadný rozdiel. Použili namiesto zásobníka (stack) frontu (queue). Tá sa od zásobníka líši tým, že zatiaľ čo pri zásobníku pridávame aj odoberáme prvky z vrchu, pri fronte pridávame prvky na vrch, ale odoberáme ich zospodu. To značne zmení, ako vyhodnotíme daný výraz.

Už je však neskoro, suma je vyplatená a program spustený. Ostáva jediné - napísať ďalší program, ktorý bude prepisovať výrazy z postfixovej notácie na takú, ktorú náš program vyhodnotí rovnako, ako by správny program so zásobníkom vyhodnotil originálnu.

Vstup a výstup

V prvom riadku vstupu je číslo \(T\) - počet výrazov, ktoré máme prepísať.

V každom z ďalších \(T\) riadkov je jeden výraz. Malé písmenká anglickej abecedy reprezentujú operandy, a veľké písmená reprezentujú operátory.

Vypíšte pre každý výraz \(A\) taký výraz \(B\), že \(A\) sa vyhodnotí postupom popísaným v úlohe so zásobníkom rovnako, ako sa vyhodnotí výraz \(B\), keď pri tom použijeme frontu. Aby bol výstup jednoznačný, budeme predpokladať že žiadny z operátorov nie je asociatívny ani komutatívny (aXb != bXa, (aXb)Xc != aX(bXc)).

Platí \(1 \leq T \leq 100\).

Výrazy budú korektné výrazy v postfixovej notácii, ich dĺžka nepresiahne \(50\,000\) znakov a súčet ich dĺžok nepresiahne \(200\,000\) znakov.

V prvej sade platí, že dĺžka výrazu je najviac \(3\) znaky.

V druhej a tretej sade platí, že dĺžka výrazu je najviac \(100\) znakov.

V posledných troch sadách neplatia žiadne obmedzenia navyše.

Príklad

Input:

3
xyPzX
aaAaaAA
abcDEfGhiJK

Output:

yxzPX
aaaaAAA
cbDaihfEJGK

V prvom výraze napushujeme do fronty y,x,z. Vyberieme z nej y a x, a pushneme (xPy). Vyberieme z, (xPy) a pushneme ((xPy)Xz). To je výraz, ktorý by vyhodnotil správny program pre xyPzX.