Bluff a descoperit recent in masina portocalie un sir $A$ de $N$ numere intregi. Instant, i-au venit in cap $M$ intrebari de forma: dandu-se o pozitie $p$ a sirului si un numar $k$, sa se afiseze a $k$-a pozitie notata $r$ din dreapta pozitiei $p$ $(r > p)$ cu proprietatea ca $A{~r~} > A{~p~}$.
Bluff isi genereaza intrebarile in felul urmator, cunoscand valorile $G$ si $H$:

p{~i~} ≤

$p{~i~} = 1 + (i + p{~i-1~}*G)%N$
$k{~i~} = 1 + (i + k{~i-1~}*H)%5$

h2. Date de intrare

Fişierul de intrare $ismquery.in$ va contine pe prima linie doua numere naturale $N$ si $M$ cu semnificatia din enunt. A doua linie va continue $N$ numere separate prin spatii, reprezentand continutul sirului $A$. Liniile intre $3$ si $M+2$ vor contine cate doua numere, separate prin spatiu, $p$, respectiv $k$, cu semnificatia din enunt.

Fişierul de intrare $ismquery.in$ va contine pe prima linie doua numere naturale $N$ si $M$ cu semnificatia din enunt. A doua linie va continue $N$ numere separate prin spatii, reprezentand continutul sirului $A$. Linia $3$ va contine numerele $G$ respectiv $H$, separate prin spatiu, cu semnificatia din enunt.

h2. Date de ieşire

În fişierul de ieşire $ismquery.out$ vor fi afisate $M$ linii, fiecare continand raspunsul la cate o intrebare , in ordinea aparitiei in fisierul de intrare. Daca pentru un query pozitia ceruta nu exista, se va afisa 0.

În fişierul de ieşire $ismquery.out$ vor fi afisate $M$ linii, fiecare continand raspunsul la cate o intrebare in ordinea generarii lor. Daca pentru un query pozitia ceruta nu exista, se va afisa 0.

h2. Restricţii

* $N ≤ 500.000$
* $M ≤ 1.000.000$
* $k{~i~} ≤ 4$ pentru orice $1 ≤ i ≤ M$

* $N ≤ 400.000$
* $M ≤ 1.200.000$
* $p{~0~} = k{~0~} = 1$
* Evident, $k{~i~} ≤ 5$ pentru orice $1 ≤ i ≤ M$

* $-2.000.000.000 ≤ A{~i~} ≤ 2.000.000.000$ pentru orice $1 ≤ i ≤ N$

* Elementele sirului $A$ si cele $M$ intrebari se numeroteaza de la $1$ la $N$

* Elementele sirului $A$ si cele $M$ intrebari se numeroteaza incepand cu $1$
* $1 ≤ G,H ≤ 1000$

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

| 5 3
  4 5 -1 7 2
  1 2
  1 3
  3 2
| 4

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

  0

  5

|
== include(page="template/taskfooter" task_id="ismquery") ==

9278