间谍

文件名

spy.cpp

题目描述

作为A国最强的间谍，克利切洛夫斯基这次又接到了一个绝密的任务，他要伪装在一些游客中潜入敌对国B国。而B国也对此早有防备，他们给每名游客都发放了一个正整数作为身份编号，这些身份编号可能重复，并对身份信息进行了M次检测。克利切洛夫斯基可以伪造自己的身份编号。

所有游客按顺序站成一排，克利切洛夫斯基开始时并不在其中。第$i$次检测会扫描游客队列中连续的一段$[L_i,Ri]$，并找出这些游客身份编号的最大公约数。这时候可以切洛夫斯基想要乘着这一次检测混入人群，那么就要保证他的身份编号与$[Li,Ri]$这些游客的身份编号的最大公约数和之前相比完全相同。同时，为了减少伪造身份的开销，他伪造的身份编号应该尽可能的小。对于每一次检测，请你回答出克利切洛夫斯基使用的最小的身份编号是多少？

输入格式

第一行输入两个整数$N$和$M$，表示游客的数量（不包括克利切洛夫斯基）和进行检测的次数。

接下来一行有$N$个整数，第$i$个整数表示每名游客的身份编号$A_i$。

接下来$M$行，其中第$i$行有两个整数$L_i$和$R_i$，分别表示检测的游客区间的左端点和右端点。

输出格式

共$M$行，每行一个整数表示对于这一次检测，克利切洛夫斯基可以使用的最小的身份编号。

样例

样例输入

5 3
4 5 6 12 10
1 2
3 4
3 5

样例输出

1
6
2

样例解释

对于第一次检测，$GCD(4,5)=1$​，克利切洛夫斯基可以使用的最小身份编号是1，$GCD(4,5,1)=1$​

对于第二次检测，$GCD(6,12)=6$，克利切洛夫斯基可以使用的最小身份编号是6，$GCD(6,12,6)=6$

对于第三次检测，$GCD(6,12,10)=2$，克利切洛夫斯基可以使用的最小身份编号是2，$GCD(6,12,10,2)=2$

提示

对于30%的数据，保证$1\leq N,M\leq 10$。

额外有30%的数据，保证$1\leq N,M\leq 1,000$且数据在范围内随机生成。

对于100%的数据，保证$1\leq N,M\leq1,000，1\leq Ai\leq 10^6,1\leq Li\leq Ri\leq N$