carray

Cerință

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 \leq i \leq 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.

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)$.

Date de ieșire

În fişierul de ieşire carray.out veţi afişa, în ordine, pentru fiecare întrebare $(i,p)$ din fişierul de intrare, numărul care se află pe poziţia $p$ din vectorul $i$.

Restricții și precizări

• $1 \leq N \leq 20 \ 000$
• $0 \leq M \leq 500 \ 000$
• $1 \leq Q \leq 20 \ 000$
• $1 \leq a(i) < i$ şi $1 \leq b(i) < i$ (pentru $N+1 \leq I \leq N + M$)
• Î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, \dots , N$ este între $0$ şi $100 \ 000 \ 000$.

Exemplu

carray.in

3 4 5
36
9
1 2
4 2
5 5
6 3
1 1
4 2
5 2
6 4
7 6

carray.out

3
6
6
3
6

Explicație

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

• vectorul $4$: $3, 6$
• vectorul $5$: $3, 6, 6$
• vectorul $6$: $3, 6, 6, 3, 6, 6$
• vectorul $7$: $3, 6, 6, 3, 6, 6, 9$