問題文

数直線上に $N$ 個の点があり，そのうち $i$ 番目の点は座標 $X_i$ にあります． これらの点は座標の昇順に番号がついています． つまり，すべての $i$ ($1 \\leq i \\leq N-1$) について，$X_i<X_{i+1}$ が成り立ちます. また，整数 $K$ が与えられます．

$Q$ 個のクエリを処理してください．

$i$ 番目のクエリでは，整数 $L_i,R_i$ が与えられます． ここで，点の集合 $s$ がよい集合であるとは，以下の条件をすべて満たすことを意味します． よい集合の定義がクエリごとに変わることに注意してください．

• $s$ に含まれる点は，$X_{L_i},X_{L_i+1},\\ldots,X_{R_i}$ のいずれかである．
• $s$ に含まれるどの異なる $2$ 点についても，その間の距離が $K$ 以上である．
• $s$ のサイズは，上記の条件を満たす集合の中で最大である．

各クエリごとに，すべてのよい集合の和集合のサイズを求めてください．

制約

• $1 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq K \\leq 10^9$
• $0 \\leq X_1 <X_2 < \\cdots < X_N \\leq 10^9$
• $1 \\leq Q \\leq 2 \\times 10^5$
• $1 \\leq L_i \\leq R_i \\leq N$
• 入力は全て整数である．

入力

入力は以下の形式で標準入力から与えられる．

$N$ $K$ $X_1$ $X_2$ $\\cdots$ $X_N$ $Q$ $L_1$ $R_1$ $L_2$ $R_2$ $\\vdots$ $L_Q$ $R_Q$

出力

各クエリごとに，すべてのよい集合の和集合のサイズを一行に出力せよ．

入力例 1

5 3
1 2 4 7 8
2
1 5
1 2

出力例 1

4
2

$1$ つめのクエリでは，最大 $3$ つの点を集合に含めることができます． よい集合は，$\\{1,4,7\\}$ と $\\{1,4,8\\}$ の $2$ つです． よって，すべてのよい集合の和集合のサイズは $|\\{1,4,7,8\\}|=4$ です．

$2$ つめのクエリでは，最大 $1$ つの点を集合に含めることができます． よい集合は，$\\{1\\}$ と $\\{2\\}$ の $2$ つです． よって，すべてのよい集合の和集合のサイズは $|\\{1,2\\}|=2$ です．

入力例 2

15 220492538
4452279 12864090 23146757 31318558 133073771 141315707 263239555 350278176 401243954 418305779 450172439 560311491 625900495 626194585 891960194
5
6 14
1 8
1 13
7 12
4 12

出力例 2

4
6
11
2
3