T390219 红藕香残

> 红藕香残玉簟秋，轻解罗裳，独上兰舟。云中谁寄锦书来？雁字回时，月满西楼。 > > 花自飘零水自流，一种相思，两处闲愁。此情无计可消除，才下眉头，却上心头。

Alice 和 Bob 在玩游戏，他们面前有一个长度为 $n$ 的正整数序列 $a$，一共有 $q$ 次游戏，每轮游戏给定 $[l,r]$，Alice 会在 $[l,r]$ 中挑选 $k$ 个数，Bob 会计算这些数的 $\gcd$ 作为自己的得分。Bob 想要知道在 Alice 的所有选择方案中，他能得到的最大得分是多少。因为 Alice 比较贪心所以她会选择比较多的数，因此在此题中 $k\geq (r-l+1)-3$。

第一行有两个正整数 $n,q$。 接下来一行，$n$ 个正整数。表示序列 $a$。 接下来 $q$ 行，每行三个正整数 $l,r,k$。

一共 $q$ 行，第 $i$ 行表示第 $i$ 场游戏的答案。

#### 「样例 #3」 见选手目录下的 ex_c3.in 与 ex_c3.ans。 这个样例满足测试点 $1\sim 5$ 的条件限制。 #### 「数据范围」 对于全部数据，$1\leq n,q\leq 10^5,\max(1,(r-l+1)-3)\leq k\leq (r-l+1),1\leq a_i\leq 10^{18}$。 | 数据点编号 | $n,q\leq$ | $k\geq $ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | | $1\sim 5$ | $50$ | $(r-l+1)-3$ | 无 | | $6\sim 7$ | $10^5$ | $(r-l+1)$ | 无 | | $8\sim 9$ | $10^5$ | $(r-l+1)-3$ | A | | $10\sim 11$ | $1000$ | $(r-l+1)-1$ | 无 | | $12\sim 13$ | $10^5$ | $(r-l+1)-1$ | 无 | | $14\sim 15$ | $10^5$ | $(r-l+1)-2$ | 无 | | $16\sim 20$ | $10^5$ | $(r-l+1)-3$ | 无 | 特殊性质 A ：保证序列 $a$ 随机生成。