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