Un vector este o secvenţă de numere naturale. Iniţial se dau N vectori, numerotaţi de la 1 la N, fiecare dintre 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).
Cerinţă
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
• 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 1016.
• 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 dintre vectorii 1, ..., N este între 0 şi 100 000 000.