#3005. 区间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 行,每行表示一个询问的答案。

样例

样例输入

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

样例输出

1
3
7

提示

  • 对于 100%100\% 的数据,1lrn10001 \leq l \leq r \leq n \leq 10001m1061\leq m \leq 10^61ai1091 \leq a_i \leq 10^9
  • 如果你不想因为超时而被罚时,那么本题目请使用scanf读入,printf输出!