题目描述

数直線上に $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$ のサイズは，上記の条件を満たす集合の中で最大である．

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

输入格式

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

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

输出格式

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

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

4
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

4
6
11
2
3

提示

制約

• $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$
• 入力は全て整数である．

Sample Explanation 1

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