[比赛/考试专用OJ] 该 OJ 与 oj.socoding.cn 数据不互通,首次使用请注册账号。

1064. 模数定理(25分)

在金属冶炼的时候虾虎队伍面对数论问题屡屡碰壁,于是身为其中一员的 Serein在 A1m的催促下苦练数论。但殊不知 Tension才是真正的数学王子,最终发现了模数定理,于是跟 Serein共同窥探此定理的玄妙。当然好的定理肯定要分享给你们,所以 Serien特地给出一道题,将其中的玄妙之处分享给你们。

Serein 有一整数数组 a,由 n 个正整数组成。给定正常数 k。现有 q 次询问,每次询问给出正整数 l,r,求长为 k+1 的区间 [l,r] 中任意两个数的余数 a_i \bmod a_j (l \leq i \leq r,l \leq j \leq r) 的最大值。

输入

第一行输入两个整数 n,k(2 \leq n \leq 2 \times 10^5,1 \leq k \leq n-1)

第二行输入 n 个整数,第 i 个整数为 a_i(1 \leq a_i \leq 10^9)

第三行输入一个整数 q(1 \leq q \leq 10^5) 代表询问次数。

接下来输入 q 行,每行两个数 l,r(1\le l < r\le n, r-l=k),代表一次询问。

输出

对于每次询问,输出一行一个整数代表 a_i \bmod a_j (l \leq i \leq r,l \leq j \leq r) 的最大值。

样例

标准输入 复制文本
3 1
1 3 2
2
1 2
2 3
标准输出 复制文本
1
2
登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 106
通过 17