Dany jest ciąg liczb całkowitych oraz pewna liczba przedziałów w tym ciągu. Przedziały są określone przez skrajne lewe i prawe pozycje. Przedział zawierający $k$ liczb ma $k(k-1)/2$ par liczb na różnych pozycjach, z których każda ma swój największy wspólny dzielnik. Dla każdego podanego przedziału znajdź największy spośród tych największych wspólnych dzielników.
Na przykład, gdy ciąg to $(a_1,\ldots,a_6)=(10,20,30,40,50,60)$, a jako przedział wskazano cały ciąg, należy rozważyć poniższe 15 par liczb na różnych pozycjach $x,y$ oraz ich największe wspólne dzielniki.
| $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$ |
W tym przypadku największy ze wspólnych dzielników 15 par wynosi $\gcd(30,60)=30$.
Wejście
Wejście zawiera jeden przypadek testowy w następującym formacie.
$$\begin{array}{l}n\\a_1\ \cdots\ a_n\\q\\l_1\ r_1\\\vdots\\l_q\ r_q\end{array}$$
Pierwszy wiersz zawiera liczbę całkowitą $n$, oznaczającą liczbę elementów ciągu, spełniającą $2\le n\le 10^5$. Drugi wiersz zawiera $n$ dodatnich liczb całkowitych $a_1,\ldots,a_n$, określających ciąg. Żadna nie przekracza $10^5$.
Trzeci wiersz zawiera dodatnią liczbę całkowitą $q$, oznaczającą liczbę przedziałów do rozważenia, nie większą niż $10^5$. Następuje po nim $q$ wierszy, z których każdy określa rozważany przedział. $i$-ty z nich zawiera dwie liczby całkowite $l_i,r_i$ ($1\le l_i<r_i\le n$), określające przedział od $a_{l_i}$ do $a_{r_i}$ w ciągu.
Wyjście
Wypisz $q$ wierszy. $i$-ty powinien zawierać największy spośród największych wspólnych dzielników wszystkich par w przedziale określonym przez $l_i,r_i$.
Przykład
Wejście 1
6 10 20 30 40 50 60 3 1 6 2 5 4 5
Wyjście 1
30 20 10
Wejście 2
10 13 2 35 4 13 2 5 1 7 4 5 1 4 4 10 3 8 3 9 1 10
Wyjście 2
2 4 5 7 13