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:
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
#include <assert.h>
#include <unordered_map>
#include <fstream>
#include <ctime>
#include <complex>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef pair<int,int> pii;
typedef vector<P> vpl;
typedef tuple<ll,ll,ll> tapu;
#define rep(i,n) for(int i=0; i<(n); i++)
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 2020000;
ll dy[8] = {1,-1,0,0,1,-1,1,-1};
ll dx[8] = {0,0,1,-1,1,-1,-1,1};
const double pi = acos(-1);
const double eps = 1e-7;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
	if(a>b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
	if(a<b){
		a = b; return true;
	}
	else return false;
}
template<typename T> inline void print(T &a){
    for(auto itr = a.begin(); itr != a.end(); itr++){
		cout << *itr << " ";
	}
    cout << "\n";
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){
	cout << "debug: " << a << " " << b << "\n";
}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << "debug: " << a << " " << b << " " << c << "\n";
}
void mark() {cout << "#" << "\n";}
ll pcount(ll x) {return __builtin_popcountll(x);}
const int mod = 1e9 + 7;
//const int mod = 998244353;

ll Lpos[20][202020], Lsum[20][202020];
ll Rpos[20][202020], Rsum[20][202020];

int main(){
    ll n,k; cin >> n >> k;
    vl x(n); rep(i,n) cin >> x[i];
    rep(i,n){
        Lpos[0][i] = lower_bound(all(x), x[i] + k) - x.begin();
        Rpos[0][i] = upper_bound(all(x), x[i] - k) - x.begin() - 1;
		Lsum[0][i] = Rsum[0][i] = i;
    }
	Lpos[0][n] = n;
	rep(i,19){
		rep(j,n){
			Lpos[i+1][j] = Lpos[i][Lpos[i][j]];
			Lsum[i+1][j] = Lsum[i][j] + Lsum[i][Lpos[i][j]];
			if(Rpos[i][j] != -1) Rpos[i+1][j] = Rpos[i][Rpos[i][j]];
			else Rpos[i+1][j] = -1;
			Rsum[i+1][j] = Rsum[i][j];
			if(Rpos[i][j] >= 0){
				Rsum[i+1][j] += Rsum[i][Rpos[i][j]];
			}
		}
		Lpos[i+1][n] = n;
	}
	int q; cin >> q;
	while(q--){
		ll l,r; cin >> l >> r; l--; r--;
		ll pos = l;
		ll ls = 0, rs = 0;
		for(int i=19; i>=0; i--){
			if(Lpos[i][pos] <= r){
				ls += Lsum[i][pos];
				pos = Lpos[i][pos];
			}
		}
		ls += pos;
		pos = r;
		for(int i=19; i>=0; i--){
			if(Rpos[i][pos] >= l){
				rs += Rsum[i][pos] + (1<<i);
				pos = Rpos[i][pos];
			}
		}
		rs += pos + 1;
		cout << rs - ls << "\n";
	}
}