Zabawa z DNA

Treść

Szalony naukowiec Adalbert zafascynował się ostatnimi czasy biologią molekularną. W szczególności interesują go łańcuchy DNA i to, co w wyniku ich modyfikacji można osiągnąć. Do pracy nad nimi skonstruował specjalną machinę. Posiada ona zasobnik nukleotydów i łańcuchów cząstkowych oraz moduł rozcinająco-klejący. W pojedynczym kroku machina rozcina konstruowany łańcuch, wybiera nukleotyd lub łańcuch cząstkowy z zasobnika i wkleja go w rozcięte miejsce. Dzięki niej Adalbert może skonstruować dowolny łańcuch DNA. Ze względu na to, iż kontrolowane eksperymenty nie przyniosły ciekawych rezultatów, naukowiec postanowił pójść na żywioł i konstruować łańcuchy losowo. Napisał specjalny program generujący ciągi rozkazów dla machiny. Pojedynczy taki rozkaz składa się z dwóch części: wklejanego łańcucha cząstkowego (lub pojedynczego nukleotydu) oraz miejsca jego wklejenia. Tym razem wyniki eksperymentów przeszły oczekiwania samego Adalberta. Niestety wraz z sukcesem pojawił się problem. Naukowiec nie potrafi teraz odtworzyć pełnego kodu łańcucha. To zadanie zlecił swemu zaufanemu asystentowi, czyli Tobie. Napisz program, który dla podanej sekwencji rozkazów wypisze kod wygenerowanego przez machinę łańcucha DNA.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

W pierwszym wierszu zestawu danych znajduje się liczba całkowita n (1<=n<=200000) rozkazów dla machiny. W kolejnych n wierszach podane są rozkazy. Na jeden rozkaz składa się nieujemna liczba całkowita m_i oraz ciąg złożony z wielkich liter A, G, C lub T, oddzielone spacją. Ciąg liter odpowiada wstawianemu łańcuchowi cząstkowemu, a liczba m_i miejscu jego wklejenia, przy czym rozcięcie następuje bezpośrednio po m_i-tym nukleotydzie łańcucha uzyskanego w i - 1 kroku. Wartość m_i równa 0 oznacza, że łańcuch cząstkowy jest wstawiany na początek istniejącego. Początkowo, przed pierwszym rozkazem, konstruowany łańcuch jest pusty. Suma długości wszystkich łańcuchów cząstkowych nie przekracza 200000 nukleotydów.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest ciąg liter odpowiadający wygenerowanemu przez machinę łańcuchowi DNA.

Przykład

dane wejściowe:
2
3
0 AAA
2 TT
1 CC
6
0 AAAT
3 CC
1 GG
4 TT
2 AA
0 CC

wynik:
ACCATTA
CCAGAAGATTACCT