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:
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int N;
LL K;
LL X[200011];

const int LOG = 18;
int Right[LOG][200011];
LL RightCnt[LOG][200011];
LL RightSum[LOG][200011];

int Left[LOG][200011];
LL LeftCnt[LOG][200011];
LL LeftSum[LOG][200011];

void MAIN() {
    scanf("%d%lld", &N, &K);
    REP (i, N) scanf("%lld", X+i);

    for (int i=0, j=0; i<N; i++) {
	while (j < N && X[j] - X[i] < K) j++;
	Right[0][i] = j;
	RightCnt[0][i] = j - i;
	RightSum[0][i] = j - i;
    }

    Right[0][N] = N;
    REP (t, LOG-1) {
	REP (i, N+1) {
	    int s = Right[t][i];
	    Right[t+1][i] = Right[t][s];
	    RightCnt[t+1][i] = RightCnt[t][i] + RightCnt[t][s];
	    RightSum[t+1][i] = RightSum[t][i] + RightSum[t][s] + (RightCnt[t][s] << t);
	}
    }

    for (int i=N-1, j=N-1; i>=0; i--) {
	while (j >= 0 && X[i] - X[j] < K) j--;
	Left[0][i] = j;
	LeftCnt[0][i] = i - j;
	LeftSum[0][i] = i - j;
    }
    REP (t, LOG-1) {
	REP (i, N) {
	    int s = Left[t][i];
	    if (s == -1) {
		Left[t+1][i] = -1;
		LeftCnt[t+1][i] = LeftCnt[t][i];
		LeftSum[t+1][i] = LeftSum[t][i];
	    } else {
		Left[t+1][i] = Left[t][s];
		LeftCnt[t+1][i] = LeftCnt[t][s] + LeftCnt[t][i];
		LeftSum[t+1][i] = LeftSum[t][s] + LeftSum[t][i] + (LeftCnt[t][i] << t);
	    }
	}
    }

    int Q;
    scanf("%d", &Q);
    REP ($, Q) {
	int L, R;
	scanf("%d%d", &L, &R);
	L--;

	LL ans = 0;
	{
	    int cur = L;
	    LL mult = 0;
	    LL sum = 0;
	    for (int t=LOG; t--;) {
		int s = Right[t][cur];
		if (s != N && s <= R) {
		    sum += RightSum[t][cur] + RightCnt[t][cur] * mult;
		    mult += 1LL<<t;
		    cur = s;
		}
	    }
	    sum += (R - cur) * (mult + 1);

	    ans += sum;
	}

	{
	    int cur = R-1;
	    LL cnt = 0;
	    LL sum = 0;
	    for (int t=LOG; t--;) {
		int s = Left[t][cur];
		if (L <= s) {
		    sum += LeftSum[t][cur] + cnt * (1LL<<t);
		    cnt += LeftCnt[t][cur];
		    cur = s;
		}
	    }

	    ans -= sum;
	}
	
	printf("%lld\n", ans);
    }

}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}