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<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,k,l,r,nxt[20][200005],pre[20][200005],q,x[200005],gl,gr;
ll sump[20][200005],sumn[20][200005],ans0,ans1;
int main()
{
	scanf("%d%d",&n,&k);
	nxt[0][n+1]=n+1;
	pre[0][n+1]=n;
	pre[0][0]=0;
	nxt[0][0]=1;
	for(int i=1;i<=n;i++)scanf("%d",&x[i]);
	x[0]=-1e9;x[n+1]=2e9;
	for(int i=1;i<=n;i++)
	{
		pre[0][i]=upper_bound(x+1,x+n+1,x[i]-k)-x-1;
		nxt[0][i]=lower_bound(x+1,x+n+1,x[i]+k)-x;
		sump[0][i]=pre[0][i];
		sumn[0][i]=nxt[0][i];
	}
	for(int i=1;i<20;i++)
	{
		for(int j=0;j<=n+1;j++)
		{
			pre[i][j]=pre[i-1][pre[i-1][j]];
			sump[i][j]=sump[i-1][j]+sump[i-1][pre[i-1][j]];
			nxt[i][j]=nxt[i-1][nxt[i-1][j]];
			sumn[i][j]=sumn[i-1][j]+sumn[i-1][nxt[i-1][j]];
			//printf("%d %d %d\n",i,j,nxt[i][j]);
		}
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&l,&r);
		gl=l;gr=r;
		ans0=0;ans1=r-l;
		for(int i=19;i>=0;i--)
		{
			//printf("%d %d %d\n",i,nxt[i][gl],r);
			if(nxt[i][gl]<=r)
			{
				ans0+=(1<<i);
				ans1-=sumn[i][gl];
				ans1+=sump[i][gr];
				//printf("%d %d %d %d %d\n",i,gl,gr,sumn[i][gl],sumn[i][gr]);
				gl=nxt[i][gl];
				gr=pre[i][gr];
			}
		}
		ans1+=ans0+1;
		printf("%lld\n",ans1);
	}
	return 0;
}