Problem: There are N points on a number line, i-th of which is placed on coordinate X_i. These points are numbered in the increasing order of coordinates. In other words, for all i (1 \leq i \leq N-1), X_i < X_{i+1} holds. In addition to that, an integer K is given.

Process Q queries.

In the i-th query, two integers L_i and R_i are given. Here, a set s of points is said to be a good set if it satisfies all of the following conditions. Note that the definition of good sets varies over queries.

* Each point in s is one of X_{L_i},X_{L_i+1},\ldots,X_{R_i}.
* For any two distinct points in s, the distance between them is greater than or equal to K.
* The size of s is maximum among all sets that satisfy the aforementioned conditions.



For each query, find the size of the union of all good sets.

Constraints

* 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
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


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


Output

For each query, print the size of the union of all good sets in a line.

Examples

Input

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


Output

4
2


Input

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


Output

4
6
11
2
3

Solution (in CPP):

Solution:
/* by Natsu Kinmoe */
#include <bits/stdc++.h>
using namespace std;
#define SZ(x)               ((int)(x).size())
#define all(x)              (x).begin(), (x).end()
#define loop(i, n)          for(int i = 0; i < (n); i++)
#define cont(i, n)          for(int i = 1; i <= (n); i++)
#define circ(i, a, b)       for(int i = (a); i <= (b); i++)
#define range(i, a, b, c)   for(int i = (a); ((c) > 0 ? i <= (b) : i >= (b)); i += (c))
#define foreach(it, v)      for(__typeof((v).begin()) it = (v).begin(); it != (v).end(); it++)
#define y0          y0O0OO00OO0OO0OO0OOO00OO0OO0O0O000OO0
#define y1          y1II11II11III11I1III11II111IIII1II1I1
#define pub         push_back
#define pob         pop_back
#define mak         make_pair
typedef long long   ll;
typedef long double lf;
const int   Inf = 0x3f3f3f3f;
const ll    INF = 0x3f3f3f3f3f3f3f3fll;
/* Source code starts here */

int n, k;

struct Tree {
	struct BIT {
		int dt[1 << 18];
		void inline add(int a, int x) {
			while(a < (1 << 18)) {
				dt[a] += x;
				a += a & -a;
			}
		}
		int inline sum(int a) {
			int res = 0;
			while(a) {
				res += dt[a];
				a -= a & -a;
			}
			return res;
		}
	} bit;

	vector<int> nei[1 << 18];
	void inline link(int a, int b) {
		nei[a].pub(b);
	}

	int fa[20][1 << 18], lvl[1 << 18], sz[1 << 18], son[1 << 18];
	void inline predfs(int now) {
		sz[now] = 1;
		cont(i, 19) fa[i][now] = fa[i - 1][fa[i - 1][now]];
		loop(i, SZ(nei[now])) {
			int to = nei[now][i];
			lvl[to] = lvl[now] + 1;
			fa[0][to] = now;
			predfs(to);
			sz[now] += sz[to];
			if(!son[now] || sz[to] > sz[son[now]]) son[now] = to;
		}
	}

	int dfn[1 << 18], tmc;
	int ro[1 << 18], tag;
	void inline dfss(int now, int rt) {
		dfn[now] = ++tmc; ro[now] = rt;
		if(son[now]) dfss(son[now], rt);
		loop(i, SZ(nei[now])) {
			int to = nei[now][i];
			if(to == son[now]) continue;
			dfss(to, to);
		}
	}

	void inline init() {
		cont(i, n) bit.add(dfn[i], i);
	}

	pair<int, int> inline find(int a, int b) {
		int lvl = 0;
		range(i, 19, 0, -1) if(fa[i][a] && (tag ? fa[i][a] >= b : fa[i][a] <= b)) {
			lvl += 1 << i;
			a = fa[i][a];
		}
		return mak(lvl, a);
	}

	int inline sum(int a, int b) {
		int res = 0;
		while(1) {
			int rt = ro[a];
			bool en = 0;
			if(lvl[rt] <= lvl[b]) {
				en = 1;
				rt = b;
			}
			res += bit.sum(dfn[a]) - bit.sum(dfn[rt] - 1);
			if(en) break;
			a = fa[0][rt];
		}
		return res;
	}
} tl, tr;

int x[1 << 18];

int main() {
	scanf("%d%d", &n, &k);
	cont(i, n) scanf("%d", x + i);
	cont(i, n) {
		int pos = upper_bound(x + 1, x + n + 1, x[i] - k) - x - 1;
		tl.link(pos, i);
		pos = lower_bound(x + 1, x + n + 1, x[i] + k) - x;
		if(pos == n + 1) pos = 0;
		tr.link(pos, i);
	}
	tl.predfs(0); tr.predfs(0);
	tl.dfss(0, 0); tr.dfss(0, 0); tl.tag = 1;
	tl.init(); tr.init();
	int q; scanf("%d", &q);
	while(q--) {
		int l, r; scanf("%d%d", &l, &r);
		pair<int, int> res = tl.find(r, l);
		int ans = res.first, pr = res.second;
		res = tr.find(l, r);
		assert(ans == res.first); int pl = res.second;
		printf("%d\n", tl.sum(r, pr) - tr.sum(l, pl) + ans + 1);
	}
	return 0;
}

/* 程序实现思路：
 * 1. 构建一棵左链树和右链树，左链树中每个节点的父亲节点在序列中为第一个能接在这个点左边的点，右同理
 * 2. 倍增，求出每棵树上每个节点的 2^i 层祖先
 * 3. 对两棵树分别进行 HLD，并用线段树维护每条链上的下标和
 * 4. 对于每个询问，先找到答案长度，将右树上对应链的下标和减去左树上对应链的下标和加上长度即为答案
 * 5. 总时间复杂度 O(k log^2 n)
 */