Se te da una secuencia de enteros y varios intervalos de la secuencia. Los intervalos se especifican mediante sus posiciones más a la izquierda y más a la derecha. Un intervalo de $k$ enteros tiene $k(k-1)/2$ pares de enteros en posiciones distintas, cada uno con su máximo común divisor. Para cada intervalo dado, halla el mayor de esos máximos comunes divisores.
Por ejemplo, si la secuencia es $(a_1,\ldots,a_6)=(10,20,30,40,50,60)$ y se especifica toda la secuencia como intervalo, deben considerarse los siguientes 15 pares de enteros en posiciones distintas $x,y$ y sus máximos comunes divisores.
| $x$ | $1$ | $1$ | $1$ | $1$ | $1$ | $2$ | $2$ | $2$ | $2$ | $3$ | $3$ | $3$ | $4$ | $4$ | $5$ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $y$ | $2$ | $3$ | $4$ | $5$ | $6$ | $3$ | $4$ | $5$ | $6$ | $4$ | $5$ | $6$ | $5$ | $6$ | $6$ |
| $a_x$ | $10$ | $10$ | $10$ | $10$ | $10$ | $20$ | $20$ | $20$ | $20$ | $30$ | $30$ | $30$ | $40$ | $40$ | $50$ |
| $a_y$ | $20$ | $30$ | $40$ | $50$ | $60$ | $30$ | $40$ | $50$ | $60$ | $40$ | $50$ | $60$ | $50$ | $60$ | $60$ |
| $\gcd(a_x,a_y)$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $20$ | $10$ | $20$ | $10$ | $10$ | $30$ | $10$ | $20$ | $10$ |
En este caso, el mayor de los máximos comunes divisores de los 15 pares es $\gcd(30,60)=30$.
Entrada
La entrada consta de un solo caso de prueba con el siguiente formato.
$$\begin{array}{l}n\\a_1\ \cdots\ a_n\\q\\l_1\ r_1\\\vdots\\l_q\ r_q\end{array}$$
La primera línea contiene un entero $n$, la cantidad de enteros de la secuencia dada, que satisface $2\le n\le 10^5$. La segunda línea contiene $n$ enteros positivos $a_1,\ldots,a_n$, que especifican la secuencia. Ninguno supera $10^5$.
La tercera línea contiene un entero positivo $q$, que especifica la cantidad de intervalos que se deben considerar y no supera $10^5$. Le siguen $q$ líneas, cada una con un intervalo de la secuencia que se debe considerar. La $i$-ésima contiene dos enteros $l_i,r_i$ ($1\le l_i<r_i\le n$), que especifican el intervalo de $a_{l_i}$ a $a_{r_i}$ de la secuencia.
Salida
Escribe $q$ líneas. La $i$-ésima debe contener el mayor de los máximos comunes divisores de todos los pares del intervalo especificado por $l_i,r_i$.
Ejemplos
Entrada 1
6 10 20 30 40 50 60 3 1 6 2 5 4 5
Salida 1
30 20 10
Entrada 2
10 13 2 35 4 13 2 5 1 7 4 5 1 4 4 10 3 8 3 9 1 10
Salida 2
2 4 5 7 13