#2654. gcd区间

gcd区间

gcd区间

题目描述

给定 nn 个正整数 a1,a2,,ana_1,a_2,\dots,a_n

mm 次询问,每次询问给定一个区间 [l,r][l,r],输出 al,al+1,,ara_l,a_{l+1},\dots,a_r 的最大公因数。

输入格式

第一行两个整数 n,mn,m。 第二行 nn 个整数表示 a1,a2,,ana_1,a_2,\dots,a_n。 以下 mm 行,每行两个整数 l,rl, r 表示询问区间的左右端点。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

1
3
7

提示

  • 对于 100%100\% 的数据,1lrn1000001 \leq l \leq r \leq n \leq 1000001m1061\leq m \leq 10^61ai1091 \leq a_i \leq 10^9