在金属冶炼的时候虾虎队伍面对数论问题屡屡碰壁,于是身为其中一员的 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 |