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