Un vector este o secvenţă de numere naturale. Iniţial se dau $N$ vectori, numerotaţi de la $1$ la $N$, fiecare din ei conţinând câte un singur număr natural. Apoi se definesc alţi $M$ vectori (numerotaţi de la $N+1$ la $N+M$). Vectorul $i$ $(N+1≤i≤N+M)$ se obţine prin concatenarea vectorilor cu numerele $a(i)$ şi $b(i)$. Prin concatenare înţelegem adăugarea elementelor lui $b(i)$, în ordine, după ultimul element din $a(i)$. În urma concatenării vectorii $a(i)$ şi $b(i)$ nu se modifică (practic, doar se creează un vector nou fără modificarea vectorilor existenţi).
Considerând cei $N+M$ vectori definiţi anterior, trebuie să răspundeţi la $Q$ întrebări de tipul $(i,p)$, având semnificaţia:

Care este numărul de pe poziţia $p$ din vectorul cu numărul $i$ ? Numerele dintr-un vector sunt numerotate de la $1$ la
numărul de elemente din cadrul vectorului.

Care este numărul de pe poziţia $p$ din vectorul cu numărul $i$ ? Numerele dintr-un vector sunt numerotate de la $1$ la numărul de elemente din cadrul vectorului.

h2. Date de intrare

Prima linie a fişierului de intrare $carray.in$ conţine trei numere naturale: $N$, $M$ şi $Q$. Următoarele $N$ linii conţin fiecare câte un număr natural. Numărul de pe a $i$-a dintre aceste linii reprezintă numărul conţinut în vectorul $i$.
Următoarele $M$ linii conţin fiecare câte două numerele naturale. A $i$-a dintre aceste $M$ linii conţine valorile $a(N+i)$ şi $b(N+i)$ (pe baza cărora se construieşte vectorul $N+i$). Următoarele $Q$ linii conţin fiecare câte două numere naturale $i$ şi $p$, reprezentând o întrebare $(i,p)$.

Prima linie a fişierului de intrare $carray.in$ conţine trei numere naturale: $N$, $M$ şi $Q$. Următoarele $N$ linii conţin fiecare câte un număr natural. Numărul de pe a $i$-a dintre aceste linii reprezintă numărul conţinut în vectorul $i$. Următoarele $M$ linii conţin fiecare câte două numerele naturale. A $i$-a dintre aceste $M$ linii conţine valorile $a(N+i)$ şi $b(N+i)$ (pe baza cărora se construieşte vectorul $N+i$). Următoarele $Q$ linii conţin fiecare câte două numere naturale $i$ şi $p$, reprezentând o întrebare $(i,p)$.

h2. Date de ieşire

* $0 ≤ M ≤ 500 000$
* $1 ≤ Q ≤ 20 000$
* $1 ≤ a(i) < i$ şi $1 ≤ b(i) < i$ $(pentru N+1 ≤ I ≤ N + M)$

* În teste, numărul de elemente ale fiecărui vector va fi cel mult egal cu $1016$.

* În teste, numărul de elemente ale fiecărui vector va fi cel mult egal cu $10^16^$.

* Argumentul $i$ al unei întrebări $(i, p)$ este cuprins între $1$ şi $N+M$.
* Argumentul $p$ al unei întrebări $(i, p)$ este cuprins între $1$ şi numărul de elemente din vectorul $i$.
* Numărul natural conţinut de fiecare din vectorii $1,...,N$ este între $0$ şi $100 000 000$.

h3. Explicaţie

Vectorii $4, 5, 6 şi 7$ conţin următoarele elemente, in  ordine:

Vectorii $4, 5, 6 şi 7$ conţin următoarele elemente, in ordine:

* vectorul $4: 3, 6$
* vectorul $5: 3, 6, 6$

4906