carray

Carray

== include(page="template/taskheader" task_id="carray") ==

Poveste şi 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≤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.

h2. Date de intrare

Fişierul de intrare $carray.in$ ...

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

În fişierul de ieşire $carray.out$ ...

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

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 20 000$
* $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 $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$.

h2. Exemplu
table(example). |_. carray.in |_. carray.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

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

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

== include(page="template/taskfooter" task_id="carray") ==

4906