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<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<list>
#include<bitset>
#include<stack>
#include<memory>
#include<numeric>
#include <utility>


using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define REP(i, n) for(int i = 0;i < (n);i++)
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=1000000007;
const llint inf=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-10;
template <class T,class U>bool chmin(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool chmax(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(const vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(const vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}

//ダブリング
//ACLにないんだけど
int main(void){
	int h,i,j,n,m,K;cin>>n>>K;
	vector<llint>X(n+2);
	X[0]=-inf;X[n+1]=inf;
	for(i=1;i<=n;i++){cin>>X[i];}
	vector<int>lgo[18];
	vector<int>rgo[18];
	vector<llint>lsum[18];
	vector<llint>rsum[18];
	for(h=0;h<18;h++){
		lgo[h].res(n+2);rgo[h].res(n+2);
		lsum[h].res(n+2);rsum[h].res(n+2);
	}
	for(i=1;i<=n;i++){
		lgo[0][i]=LBI(X,X[i]+K);
		rgo[0][i]=UBI(X,X[i]-K)-1;
		lsum[0][i]=i;
		rsum[0][i]=i;
	}
	lgo[0][0]=0;lgo[0][n+1]=n+1;
	lsum[0][0]=0;lsum[0][n+1]=n+1;
	rgo[0][0]=0;rgo[0][n+1]=n+1;
	rsum[0][0]=0;rsum[0][n+1]=n+1;
	for(h=1;h<18;h++){
		for(i=0;i<=n+1;i++){
			lgo[h][i]=lgo[h-1][lgo[h-1][i]];
			rgo[h][i]=rgo[h-1][rgo[h-1][i]];
			lsum[h][i]=lsum[h-1][i]+lsum[h-1][lgo[h-1][i]];
			rsum[h][i]=rsum[h-1][i]+rsum[h-1][rgo[h-1][i]];
		}
	}
	int Q;cin>>Q;
	while(Q--){
		int L,R,gL,gR,Lcou=0,Rcou=0;cin>>L>>R;
		gL=L;gR=R;
		llint ans=0;
		for(h=17;h>=0;h--){
			if(lgo[h][gL]<=R){ans-=lsum[h][gL];gL=lgo[h][gL];Lcou+=(1<<h);}
			if(rgo[h][gR]>=L){ans+=rsum[h][gR];gR=rgo[h][gR];Rcou+=(1<<h);}
		}
		ans-=gL;Lcou++;
		ans+=gR;Rcou++;
		if(Lcou!=Rcou){cerr<<"bag"<<endl;}
		
		ans+=Lcou;
		cout<<ans<<endl;
	}
	return 0;
}