P1890 GCD Interval

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$.

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.

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

- 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