În Bistriţa sunt N copii, fiecare dintre ei având un număr preferat Xi . Copii se aşează pe un rând, cu poziţiile numerotate de la 1 la N. După ce copii s-au aşezat, profesoara de educaţie fizică le cere să execute M mişcări de tipul (a, b), cu semnificaţia că îşi vor schimba ordinea copiii care se află între poziţiile a şi b, inclusiv.

Cerință

Să se răspundă la Q întrebări de tipul p, cu semnificaţia: care este numărul preferat al copilului, care se află pe poziţia p, după executarea mişcărilor cerute de profesoara de educaţie fizică.

Date de intrare

Fișierul copii.in are pe prima linie un număr natural N. Pe linia a 2-a sunt N numere Xi , separate prin câte un spațiu, cu semnificaţia din enunţ. Pe linia a 3-a este numărul M. Pe următoarele M linii se găseșc câte un două numere a şi b cu semnificația de mai sus. Pe următoarea linie se află numărul Q. Pe următoarele linii se află câte un număr p, cu semnificaţia de mai sus.

Date de ieșire

Fișierul copii.out va conține Q linii. Pe fiecare linie se va afla răspunsul la întrebarea respectivă din fişierul de intrare

Restricții

• 1 ≤ N ≤ 100.000
• 1 ≤ M ≤ 10.000
• 1 ≤ Q ≤ 100
• 1 ≤ a ≤ b ≤ N
• -2.000.000.000 ≤ Xi ≤ 2.000.000.000

Exemplu

copii.in

10
1 2 3 4 5 6 7 8 9 10
2
2 5
4 8
6
1
2
4
5
8
10

copii.out

1
5
8
7
3
10

Explicaţie

După prima mişcare şirul format din numerele preferate ale copiilor devine: 1 5 4 3 2 6 7 8 9 10.