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 GWj
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define fastio ios::sync_with_stdio(false)
#define R(a) cin>>a
#define R2(a,b) cin>>a>>b
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
int n,k,x[200000+20],q,f[200000+20][19],ff[200000+20][19];
LL s[200000+20][19],ss[200000+20][19];
LL solve(int l,int r){
	int can=0;
	int now=l;
	rl(i,18,0)
		if(f[now][i]<=r) now=f[now][i],can|=1<<i;
	if(can==0) return r-l+1;
	LL one,two;
	one=two=0;
	now=l;
	rl(i,18,0)
		if((can>>i)&1){
			one+=s[now][i];
			now=f[now][i];	
		}
	now=r;
	rl(i,18,0)
		if((can>>i)&1){
			two+=ss[now][i];
			now=ff[now][i];
		}
	one+=l;
	two+=r;
	return two-one+can+1;
}
int main(){
	fastio;
	R2(n,k);
	rb(i,1,n)
		R(x[i]);
	rb(i,1,n+1)
		fill(f[i],f[i]+19,n+1);
	int is=n+1;
	rl(i,n,1){
		while(x[is-1]-x[i]>=k){
			is--;
		}
		f[i][0]=is;
		s[i][0]=is;
	}
	is=0;
	rb(i,1,n){
		while(x[i]-x[is+1]>=k){
			is++;
		}
		ff[i][0]=is;
		ss[i][0]=is;
	}
	rb(i,1,18)
		rb(j,1,n)
			f[j][i]=f[f[j][i-1]][i-1],ff[j][i]=ff[ff[j][i-1]][i-1],s[j][i]=s[f[j][i-1]][i-1]+s[j][i-1],ss[j][i]=ss[ff[j][i-1]][i-1]+ss[j][i-1];
	R(q);
	while(q--){
		int l,r;
		R2(l,r);
		cout<<solve(l,r)<<endl;
	}
	return 0;
}
/** 程序框架：
  * f_{i,j}=f_{f_{i,j-1},j-1}\\
  * s_{i,j}=s_{i,j-1}+s_{f_{i,j-1},j-1}
  * 
  * 
  *
  **/