题目描述

给你 \(n\) 个数（编号 \(1 \sim n\)）,然后有 \(m\) 个询问，每个询问一个区间，问你这个区间的 \(\texttt{gcd}\) 是多少。

格式

输入格式

第一行n和m

第二行n个不超过10^9的正整数；

以下 \(m\) 行每行两个数 \(l\) 和 \(r\)，表示询问区间 \(l,r\) \((l<=r)\)；

输出格式

\(m\) 行，每行针对一个询问的答案。

样例1

输入样例1

10 10
58 18 24 36 12 56 10 30 42 49
2 4
4 9
2 8
4 6
1 9
2 10
4 5
7 9
2 5
9 10

输出样例1

6
2
2
4
2
1
12
2
6
7

限制

时间：\(1s\) 空间：\(128M\)

对于 \(30\%\) 的数据：\(1<=n,m<=1000\);

对于 \(70\%\) 的数据：\(1<=n,m<=100,000\);

对于 \(100\%\) 的数据：\(1<=n,m<=500,000\);

来源

地址：\(zloj,J2021\)域
作者：\(jialiang2509\)
模拟赛\(T2\)