gcd区间

题目描述

给定一行n个正整数a[1]..a[n]。 m次询问,每次询问给定一个区间[L,R],输出a[L]..a[R]的最大公因数。

输入输出格式

输入格式


第一行两个整数n,m。 第二行n个整数表示a[1]..a[n]。 以下m行,每行2个整数表示询问区间的左右端点。 保证输入数据合法。

输出格式


共m行,每行表示一个询问的答案。

输入输出样例

输入样例 #1

5 3
4 12 3 6 7
1 3
2 3
5 5

输出样例 #1

1
3
7

说明

对于30%的数据,n <= 100, m <= 10 对于60%的数据,m <= 1000 对于100%的数据,1 <= n <= 1000,1 <= m <= 1,000,000 0 < 数字大小 <= 1,000,000,000