题目描述

给你 $n$ 个数，再给你 $q$ 次询问，每次询问一个区间 $[l,r]$，求这个区间的最大公约数。

输入格式

第一行两个整数 $n$，$q$（$1<=n,q<=2\times10^5$）表示数字的个数以及询问的个数。 第二行 $n$ 个整数，第 $i$ 个整数为 $a_i$($1<=a_i<=2\times10^5$)。 接下来 $q$ 行，每行两个整数 $l,r$，表示每一次询问

输出格式

输出 $q$ 行，表示每次询问的答案。

样例 1

样例输入 1

5 5
1 7 2 4 8
1 3
3 4
3 5
1 5
4 5

样例输出 1

1
2
2
1
4

样例 2

样例输入 2

6 5
2 6 3 5 10 15
1 3
2 3
4 5
1 2
4 6

样例输出 2

1
3
5
2
5