Fişierul $deletegcd.in$ conţine $q+2$ linii.
Pe prima linie apar $n$ şi $q$.

Pe următoarea linie apar $n$ numere,reprezentând elementele şirului $A$ .
Pe urmatoarele $q$ linii apar câte 2 numere,reprezentând parametrii $l$ şi $r$ pentru cele $q$ query-uri.

Pe următoarea linie apar $n$ numere, reprezentând elementele şirului $A$ .
Pe urmatoarele $q$ linii apar câte 2 numere, reprezentând parametrii $l$ şi $r$ pentru cele $q$ query-uri.

h2. Date de ieşire

* $1 ≤ Q ≤ 10^6^$
* $1 ≤ l < r ≤ N$
* $1 ≤ A[i] ≤ 10^6^$

* Toate secventele din întrebări au lungime cel puţin 3.
* Pentru $15$ puncte, $1 ≤ N, Q, A[i] ≤ 10^2^$
* Pentru alte $20$ de puncte $1 ≤ N, Q, A[i] ≤ 10^3^$
* Pentru alte $40$ de puncte $1 ≤ N, Q, A[i] ≤ 2*10^5^$
* Pentru restul de $25$ de puncte, se aplică restricţiile iniţiale

* Toate secvenţele din întrebări au lungime cel puţin 3.
* *Atenţie!Testele sunt grupate*
* $Pentru 15 puncte, 1 ≤ N, Q, A[i] ≤ 10^2^ (grupa testelor 1-3)$
* $Pentru alte 20 de puncte 1 ≤ N, Q, A[i] ≤ 10^3^ (grupa testelor 4-7)$
* $Pentru alte 40 de puncte 1 ≤ N, Q, A[i] ≤ 2*10^5^ (grupa testelor 8-15)$
* $Pentru restul de $25$ de puncte, se aplică restricţiile iniţiale (grupa testelor 16-20)$

* *ATENŢIE! Se recomandă parsarea fişierului $deletegcd.in$. Puteţi folosi codul oferit de noi pe siteul 'in':http://www.infoarena.ro/parsare-fisier-intrare (atât pentru utilizatorii de $C++$ şi sintaxă similară cu $fstream$, cât şi pentru iubitorii de $C$ pur)*
* *De asemenea, se recomandă să afişaţi ieşirea ca un şir de caractere (nu câte un caracter).*