stringuri

Cerință

Ana are $N$ string-uri cu indici de la $0$ la $N-1$. În fiecare din cele $Q$ zile (cu indici de la $0$ la $Q-1$), Bogdan vrea să ia 2 string-uri de la Ana, să le concateneze și să îi înapoieze Anei string-ul rezultat. Cum Bogdan este precaut, a notat indicii string-urilor concatenate în fiecare zi, însa, fiind uituc, nu mai știe care este ultimul string pe care i l-a dat Anei. Acum, el vă roagă să îl ajutați, iar el vă va răsplăti cu 100 de puncte daca reușiți.

Date de intrare

Pe prima linie a fișierului de intrare stringuri.in se găsesc două numere întregi, $N$ și $Q$.
Pe următoarele $N$ linii se găsesc string-urile inițiale ale Anei.
Pe următoarele $Q$ linii se găsesc câte 2 numere naturale $a_i$ si $b_i$ care reprezintă string-urile concatenate (a_i e primul, b_i al doilea).

Date de ieșire

Pe prima linie a fișierului de ieșire stringuri.out se va găsi ultimul string pe care Bogdan i-l dă Anei.

Restricții și precizări

• $1 \leq N, Q \leq 300 \ 000$;
• Suma lungimilor celor $N$ string-uri este $\leq 600 \ 000$
• În fiecare zi, cele 2 string-uri alese se elimină și se creează un string nou cu indice $n+i$ (pentru ziua cu indicele $i$);
• $0 \leq a_i, b_i \leq n+i-1$;
• se garantează că $a_i, b_i$ nu au fost alese înainte de ziua $i$.

Exemplul 1

stringuri.in

3
abc
def
ghi
2
0 1
3 2

stringuri.out

abcdefghi

Explicație

Prima dată, Bogdan ia abc și def și face string-ul abcdef cu indicele 3. Apoi, el ia abcdef și ghi și le concatenează.

Exemplul 2

stringuri.in

5
k
f
bb
ew
aq
4
3 4
2 5
0 6
7 1

stringuri.out

kbbewaqf