### 问题描述 对于某个序列 $b$，定义函数 $f(b)$ 如下： $b$ 中的最小值记为 $x_{min}$。对于 $b$ 中的每个最大值 $x_{max}$，将其变为 $x_{max} \mod x_{min}$，即 $x_{max}$ 对 $x_{min}$ 取模的结果。特别地，如果 $x_{max} \mod x_{min} = 0$，则将 $x_{max}$ 变为 $x_{min}$。重复这个操作直到 $b$ 中所有元素相同，则 $f(b)$ 即为这个相同元素的值。 例如，$b = [2,3,6]$，则经过数次操作后 $b$ 的变化为： $[2,3,6] \ rightarrow [2,3,2] \rightarrow [2,1,2] \rightarrow [1,1,1]$，因此$f(b) = 1$。 现在给出长度为 $n$ 的序列 $a$ 和 $q$ 组询问。每组询问包括两个端点 $l,r$。令 $a[l,r]$ 表示 $a$ 的起点为 $l$ 终点为 $r$ 的子序列，对于每组询问，你需要求 $f(a[l,r])$ 的值。需要注意的是，**每组询问是独立的**，即每个询问都是在初始的序列 $a$ 上进行的。 ### 输入格式 第一行输入两个整数 $n,q \space(1 \leq n,q \leq 10^5)$，代表序列 $a$ 的长度和询问个数。 接下来一行 $n$ 个整数 $a_i \space (1 \leq a_i \leq 10^9)$，代表序列 $a$ 的值。保证序列 $a_i$ 中任意两个元素均不相同且元素是随机生成的。 接下来 $q$ 行，每行两个整数 $l,r \space (1 \leq l \leq r \leq n)$，代表询问的区间。 ### 输出格式 输出 $q$ 行，每行一个整数，代表该询问对应的 $f(a[l,r])$ 的值。 ### 样例输入 ``` 6 4 1 4 6 3 12 8 1 6 3 4 2 3 3 5 ``` ### 样例输出 ``` 1 3 2 3 ```