Închisoare

- Bă, care este al milionulea?
- Nu știu frate, hai să îl întrebăm pe geamăn.

Cerință

Dorel este șeful celei mai mari închisori din România. Aceasta are o simplă problemă, care îi afectează grav reputația: în fiecare zi evadează câte un prizonier. Fiind o închisoare imensă, în aceasta se află $10^9 - 1$ prizonieri, numerotați de la $2$ la $10^9$. Dorel dorește să rezolve această problemă, așa că a recrutat $N$ polițiști, numerotați de la $1$ la $N$, care să patruleze perimetrul penitenciarului. Polițistul $i$ are puterea $P_i$. Un deținut cu numărul $d$ este prins de polițistul $i$ dacă $P_i|d$ (numărul deținutului $d$ este divizibil cu $P_i$).

În fiecare zi, toți prizonierii încearcă să evadeze în ordine crescătoare a numărului lor (de la $2$ la $10^9$). Un prizonier poate evada dacă nu este prins de niciun polițist activ. După ce un prizonier evadează, Dorel baricadează toate ieșirile din închisoare până în următoarea zi. Astfel, niciun alt prizonier nu mai poate evada în ziua respectivă.

Dorel este șeful închisorii doar pentru $Q$ zile (după i se termină free trial-ul). În fiecare zi, acesta încearcă o configurație nouă de polițiști, așa că, în ziua $i$, polițiștii activi vor fi cei cu numărul de ordine între $St_i$ și $Dr_i$ (un polițist $j$ este activ în ziua $i$ dacă $St_i \leq j \leq Dr_i$). Dorel v-a angajat pe voi pentru a-i spune, în fiecare zi, ce prizonier reușește să evadeze.

Zilele sunt independente una de cealaltă (Dorel reușește să aducă înapoi prizonierul care a evadat în ziua anterioară)! De exemplu, prizonierul $X$ poate evada în două zile diferite.

Date de intrare

Pe prima linie a fișierului de intrare inchisoare.in se găsesc două numere întregi, $N$ și $Q$, reprezentând numărul de polițiști recrutați de Dorel, respectiv numărul de zile în care acesta conduce închisoarea.
Pe a doua linie se găsesc $N$ numere întregi, separate printr-un spațiu, reprezentând puterea $P_i$ a fiecărui polițist.
Pe următoarele $Q$ linii, se găsesc două numere întregi, $St_i$ și $Dr_i$, reprezentând configurația de polițiști aleasă de Dorel în ziua $i$.

Date de ieșire

Pe următoarele $Q$ linii ale fișierului de ieșire inchisoare.out se va găsi un număr întreg, reprezentând numărul de ordine al prizonierului care evadează în ziua $i$ (în ordinea zilelor din fișierul de intrare).

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$;
• $1 \leq Q \leq 50$;
• $2 \leq P_i \leq 10^9$, pentru $1 \leq i \leq N$;
• $1 \leq St_i \leq Dr_i \leq N$, pentru $1 \leq i \leq Q$;
• Se poate demonstra că evadează un singur prizonier în fiecare zi;
• Zilele sunt independente una de cealaltă;

Exemplu

inchisoare.in

10 2
14 6 2 3 7 9 19 100 5 12
2 7
3 9

inchisoare.out

5
11

Explicație

În prima zi, Dorel alege polițiștii cu puterile $6, 2, 3, 7, 9, 19$.

• Prizonierul cu numărul $2$ este prins de polițistul $3$ cu $P_3=2$.
• Prizonierul cu numărul $3$ este prins de polițistul $4$ cu $P_4=3$.
• Prizonierul cu numărul $4$ este prins de polițistul $3$ cu $P_3=2$.
• Prizonierul cu numărul $5$ nu este prins de niciunul din polițiștii activi, așa că reușește să evadeze.

În a doua zi, sunt aleși polițiștii cu numărul de ordine între $3$ și $9$. Prizonierul care evadează este $11$.