#P18176. Max GCD

Max GCD

Max GCD

给定一个长度为 nn 的正整数数组 aa,下标从 1 开始。定义区间 [l,r][l,r] 的价值为

$$\max_{\substack{l\le i<j<k\le r\\j-i\le k-j}} \gcd(a_i,a_j,a_k).$$

也就是说,需要选择三个不同下标,满足左边两个下标的距离不大于右边两个下标的距离,求三数最大公约数的最大值。距离相等允许;这三个位置不要求连续。

如果区间中不足三个元素,即 r−l≤1r-l\le1,定义价值为 0。

给出 qq 个询问,每个询问要求计算一个区间的价值。数组不会修改。

输入格式

第一行两个整数 n,qn,q,满足 3≤n≤1500003\le n\le150000、1≤q≤1000001\le q\le100000。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,满足 1≤ai≤1061\le a_i\le10^6。

接下来 qq 行,每行两个整数 l,rl,r,满足 1≤l≤r≤n1\le l\le r\le n,表示一个询问。

输出格式

对每个询问输出一行一个整数,表示对应区间的价值。答案不取模。

样例

输入:

8 8
8 24 4 6 6 7 3 3
1 5
2 6
3 7
5 8
4 8
1 3
2 5
3 8

输出:

4
2
3
1
3
4
2
3