U174986 区间最大公约数

给定 $n$ 个数 $a_1....a_n$ 以及 $m$ 次询问 $l,r$，对于每次询问求出 $[l,r]$ 之间所有数的最大公约数。

第一行两个整数 $n,m$。 第二行 $n$ 个整数，表示 $a_1...a_n$。 接下来 $m$ 行，每行两个整数 $l_i,r_i$，表示询问 $[l_i,r_i]$ 区间内的最大公约数。

共 $m$ 行，对于每次询问输出一个整数，表示询问的答案。

**本题采用~~绑架~~捆绑测试。** 对于 $10\%$ 的数据，$1 \leq n,m \leq 3 \times 10^3$。 对于 $30\%$ 的数据，$1 \leq n \leq 3 \times 10^3$，$1 \leq m \leq 4 \times 10^5$。 对于 $60\%$ 的数据，$1 \leq n,m \leq 4 \times 10^5$。 对于 $100\%$ 的数据，$1 \leq n,m \leq 3 \times 10^6,1 \leq a_i \leq 2^{31}-1$。 - 我想试试卡线段树的数据：对于额外的 20 分 $1 \leq n \leq 10^6, 1 \leq m \leq 6 \times 10^6, 1 \leq a_i \leq 100$。