Zadanie

Jaroslavov darček

Počet bodov: 75

Za chvílu sú Vianoce!

Tešia sa všetci, a najmä Jaroslav.

A nič nepokazí pekné vianoce ako riadne náročná domáca úloha na zimné prázdniny.

Jaroslav nanešťastie práve takú dostal. Napadlo ho však kreatívne riešenie - vypýta si vypracovanú úlohu už od Santa Clausa, a potom si môže predvianočný čas pokojne užívať.

Santa si nervózne číta Jaroslavov zoznam prianí, ktorý mu doniesli vystrašení škriatkovia. Hasičské autíčko v detskej veľkosti, mobil ktorému nedochádza baterka, striebornú rybičku… domácu úlohu?

A škriatkovia mu už do ruky vtískajú priloženú obálku s domácou úlohou z informatiky. Santa Claus je však dosť staromódny, a informatike sa nerozumie.

Jaroslav však bol na zozname dobrých detí, tak jeho želania treba splniť!

Nakoniec však prišiel s riešením - pomocní škriatkovia nie sú zas tak odlišní od riešiteľov Zenitu, môžu mu s ňou predsa pomôcť…

Úloha

Zadefinujeme si najprv niekoľko pojmov.

Halda je zakorenený strom, v ktorom majú vrcholy hodnoty. Hodnoty v synoch vrchola sú menšie ako jeho hodnota. Vďaka tomu je napríklad v koreni stromu vždy najväčšia hodnota.

Binárny vyhľadávací strom je strom, v ktorom majú vrcholy nápisy. Každý vrchol môže mať ľavého a/alebo pravého syna, a platí že všetky nápisy v jeho ľavom podstrome sú menšie ako jeho nápis, a všetky nápisy v jeho pravom podstrome sú väčšie ako jeho nápis.

Strom v ktorom majú vrcholy aj hodnoty aj nápisy, a je zároveň Haldou a Binárnym vyhľadávacím stromom, sa nazýva Treap.

Jaroslavova domáca úloha je jednoduchá - dostal nejaké vrcholy s navzájom rôznymi nápismi a hodnotami, a má z nich postaviť Treap.

Vstup a Výstup

V prvom riadku vstupu je číslo \(t\) - počet zadaní Jaroslavovych úloh.

Každá úloha je popísaná dvoma riadkami - v prvom riadku je číslo \(n\) - počet vrcholov ktoré Jaroslav dostal - a v druhom riadku sú tieto vrcholy v tvare <napis>/<hodnota>.

Pre každú domácu úlohu vypíšte Treap týchto vrcholov vo formáte (<lavy podstrom><napis>/<hodnota><pravy podstrom>). Podstromy sa vypisujú rekurzívne, a nie ak sú prázdne. Pozrite si príklady.

Platí \(1 \leq t \leq 69\), \(1 \leq n \leq 50\,000\), \(1 \leq |napis| \leq 5\), \(0 \leq hodnota \leq 100\,000\), a súčet \(n\) v jednom vstupe bude \(\leq 200\,000\).

Nápisy aj hodnoty sú navzájom rôzne. Nápisy sú z malých písmen anglickej abecedy.

Sú dve sady vstupov. V prvej navyše platí \(n \leq 1000\).

Príklad

Input:

3
7
abcd/7 bcde/6 ccc/5 dada/4 este/3 fuha/2 good/1
7
anna/1 betka/2 cyril/3 dorka/4 egor/5 fezjo/6 greta/7
7
ahaha/3 bebe/6 cici/4 dodo/7 ehehe/2 fufu/5 gaga/1

Output:

(abcd/7(bcde/6(ccc/5(dada/4(este/3(fuha/2(good/1)))))))
(((((((anna/1)betka/2)cyril/3)dorka/4)egor/5)fezjo/6)greta/7)
(((ahaha/3)bebe/6(cici/4))dodo/7((ehehe/2)fufu/5(gaga/1)))