Description

Given $n$ positive integers $a_1, a_2, \dots, a_n$.

There are $m$ queries. For each query, given an interval $[l, r]$, output the greatest common divisor of $a_l, a_{l+1}, \dots, a_r$.

Input Format

The first line contains two integers $n, m$.
The second line contains $n$ integers representing $a_1, a_2, \dots, a_n$.
Each of the next $m$ lines contains two integers $l, r$ representing the left and right endpoints of the query interval.

Output Format

Print $m$ lines, each line is the answer to one query.

5 3
4 12 3 6 7
1 3
2 3
5 5

1
3
7

Hint

• For $30\%$ of the testdata, $1 \leq n \leq 100$, $1 \leq m \leq 10$.
• For $60\%$ of the testdata, $1 \leq m \leq 1000$.
• For $100\%$ of the testdata, $1 \leq l \leq r \leq n \leq 1000$, $1 \leq m \leq 10^6$, $1 \leq a_i \leq 10^9$.

Translated by ChatGPT 5