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