最大GCD

题号：NC200199
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 58 M，其他语言116 M
64bit IO Format: %lld

题目描述

给出长度为n的序列，序列中有 ${n}$ 个元素 ${a_{1},a_{2}...a_{n}}$ ，你需要进行 ${q}$ 次查询，每次查询形如以下格式：

${l}$ ${r}$ ${x}$ ：你需要选择两个整数 ${s,t}$ 满足 ${l<=s<=t<=r}$ ，使得 ${gcd(a[s],a[s+1]...a[t-1],a[t],x)}$ 最大化。

第一行两个整数
第二行n个整数
接下来行每行三个整数表示一个查询

对于每个查询输出一个整数表示的最大值。

示例1

复制

复制

3
2