#P18663. Barkley
Barkley
Barkley
Pigetown 有 只小猪,它们都精通算法竞赛。第 只小猪的评级为 。若若干只小猪组成一个队伍,队伍的评级就是所有队员评级的最大公约数。
接下来恰好会举行 场比赛,Pigetown 每场可以派出一支队伍。对于第 场比赛,只有编号在 到 之间的小猪有时间参赛。然而由于资金不足,这个区间内恰好 只小猪必须为 Putata 和 Budada 工作以筹集经费,其余所有小猪都会参赛。
作为 Pigetown 的教练,你需要为每场比赛恰当地挑选参赛小猪,使队伍的评级最大。
输入格式
第一行包含两个整数 ,满足 、。
第二行包含 个整数 ,满足 ,表示各只小猪的评级。
接下来的 行,第 行包含三个整数 ,满足
$$1\le l_i\le r_i\le n,\qquad 1\le k_i\le\min(3,r_i-l_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