题目描述

给定一行n个正整数a[1]..a[n]。

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

输入格式

第一行两个整数n，m。

第二行n个整数表示a[1]..a[n]。

以下m行，每行2个整数表示询问区间的左右端点。

保证输入数据合法。

输出格式

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

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

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