You are given an array $A$ of integers of size $N$.

You will be given $Q$ queries. Each query consists of two integers $L$ and $R$, representing a range $[L, R]$ (inclusive, 1-based indexing). For each query, you must find the Greatest Common Divisor (GCD) of the array after excluding all elements from index $L$ to $R$ inclusive.

It is guaranteed that after excluding this subarray, the remaining array is non-empty.

The first line contains two integers $N$ and $Q$ ($2 \leq N \leq 10^5$, $1 \leq Q \leq 10^5$) --- the size of the array and the number of queries.
The second line contains $N$ integers $A_1, A_2, \ldots, A_N$ ($1 \leq A_i \leq 10^9$) --- the elements of the array.
The next $Q$ lines each contain two integers $L$ and $R$ ($1 \leq L \leq R \leq N$), representing a query.

For each query, output a single line containing one integer --- the GCD of the array after excluding the segment from $L$ to $R$ inclusive.