#P18663. Barkley

    ID: 17999 传统题 1000ms 1024MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-欧几里得算法ST 表有限候选集缩减支配关系深度优先搜索最优性剪枝

Barkley

Barkley

Pigetown 有 nn 只小猪,它们都精通算法竞赛。第 ii 只小猪的评级为 aia_i。若若干只小猪组成一个队伍,队伍的评级就是所有队员评级的最大公约数。

接下来恰好会举行 qq 场比赛,Pigetown 每场可以派出一支队伍。对于第 ii 场比赛,只有编号在 lil_i 到 rir_i 之间的小猪有时间参赛。然而由于资金不足,这个区间内恰好 kik_i 只小猪必须为 Putata 和 Budada 工作以筹集经费,其余所有小猪都会参赛。

作为 Pigetown 的教练,你需要为每场比赛恰当地挑选参赛小猪,使队伍的评级最大。

输入格式

第一行包含两个整数 n,qn,q,满足 1≤n≤1051\le n\le10^5、1≤q≤666661\le q\le66666。

第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n,满足 1≤ai≤10181\le a_i\le10^{18},表示各只小猪的评级。

接下来的 qq 行,第 ii 行包含三个整数 li,ri,kil_i,r_i,k_i,满足

$$1\le l_i\le r_i\le n,\qquad 1\le k_i\le\min(3,r_i-l_i).$$

保证 ki=1k_i=1 的询问不超过 6600066000 个,ki=2k_i=2 的询问不超过 660660 个,ki=3k_i=3 的询问不超过 66 个。

各场比赛独立选择队员,不会改变数组。评级均为正数,每个询问删除后至少保留一只小猪。

输出格式

输出 qq 行,第 ii 行包含一个整数,表示第 ii 场比赛能够获得的最大队伍评级。

样例输入 1

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

样例输出 1

3
2
3
6