数月后，果冻在原本的时空里到达了来无回之都千层塔底层后，只发现了一扇被用过的一次性传送门。正当果冻纳闷之时，一个神秘人出现在果冻眼前。神秘人自称云烟，并告知了果冻他在底层悄悄目击的一切。随后，云烟带领果冻继续下行，在最终极之渊找到了另一扇传送门，于是，他们又来到了异世界。在云烟的帮助下，果冻花费了更短的时间就完成了之前的事情——他们再次找来了禾枫、成立了公司、并先后发布了二次元卡牌手游 ONU 和游戏 果核大陆，再次走向巅峰。

然而好景不长，弥明他们的学堂成了世界一流大学，培养了无数人才，这些人才开创了异世界新时代，竞争公司如雨后春笋般涌现，果冻的公司迎来了危机。在此存亡之际，云烟打算对公司团队进行大刀阔斧的改革。

团队共有 n 人，工号从 1 到 n 递增，工号为 i 的员工的性格值为 a_i 。云烟要把团队分成若干个子团队，他发现，若一个团队里所有人性格值的最大公因数越大，这个团队就越有竞争力。所以云烟迫切想快速计算出一个团队的性格值最大公因数。

输入一行两个整数 n,m(1\le n\le10^5,1\le m\le2.3\times10^6) ，代表团队总人数和询问个数

接下来输入一行 n 个整数，第 i 个整数代表工号为 i 的人的性格值为 a_i(1\le a_i\le10^9)

接下来输入 m 行，每行两个整数 l,r(1\le l\le r\le n) ，代表由工号在区间 [l,r] 内的员工组成的一个子团队

对于每个询问，输出一行一个整数，代表这个子团队的性格值最大公因数