Pigetown 有 $n$ 只小猪。它们都精通程序设计竞赛，第 $i$ 只小猪的评分为 $a_i$。如果若干名选手组成一支队伍，那么该队伍的评分就是这些选手评分的最大公约数。

总共将举行 $q$ 场比赛。Pigetown 在每场比赛中可以派出恰好一支队伍参赛。对于第 $i$ 场比赛，只有编号在 $l_i$ 到 $r_i$ 之间的小猪有时间参赛。不幸的是，由于资金短缺，编号在 $l_i$ 到 $r_i$ 之间的猪中，必须有恰好 $k_i$ 只猪去为 Putata 和 Budada 工作以赚取资金。其余在区间内的所有猪都将参加比赛。

作为 Pigetown 的教练，你需要为每场比赛合理选择参赛的小猪，使得队伍的评分最大化。

输入格式

第一行包含两个整数 $n, q$ ($1 \le n \le 10^5, 1 \le q \le 66666$)。

接下来一行包含 $n$ 个整数，其中第 $i$ 个数为 $a_i$ ($1 \le a_i \le 10^{18}$)，表示第 $i$ 只小猪的评分。

接下来的 $q$ 行，每行包含三个整数 $l_i, r_i, k_i$ ($1 \le l_i \le r_i \le n, 1 \le k_i \le \min(3, r_i - l_i)$)，表示一场比赛。

保证 $k_i = 1$ 的比赛不超过 $66000$ 场，$k_i = 2$ 的比赛不超过 $660$ 场，$k_i = 3$ 的比赛不超过 $6$ 场。

输出格式

输出 $q$ 行，第 $i$ 行包含第 $i$ 场比赛中参赛队伍的最大评分。

样例

样例输入 1

4 4
3 2 6 4
1 3 1
2 4 1
1 4 2
1 4 3

样例输出 1

3
2
3
6