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 ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline int rd_int(void){
  int x;
  rd(x);
  return x;
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(long long x){
  int s=0;
  int m=0;
  char f[20];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    my_putchar_unlocked('-');
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
int N;
int K;
int X[200000];
int L;
int R;
int go[20][200000];
long long gos[20][200000];
int bk[20][200000];
long long bks[20][200000];
int main(){
  int jbtyPBGc;
  int i;
  int j;
  int k;
  int mx;
  long long s1;
  long long s2;
  rd(N);
  rd(K);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){
      rd(X[Lj4PdHRW]);
    }
  }
  j = 0;
  for(i=(0);i<(N);i++){
    while(j < N && X[j] < X[i]+K){
      j++;
    }
    go[0][i] = j;
    gos[0][i] = j;
  }
  j = N-1;
  for(i=(N)-1;i>=(0);i--){
    while(j >= 0 && X[j] > X[i]-K){
      j--;
    }
    bk[0][i] = j;
    bks[0][i] = j;
  }
  for(k=(1);k<(20);k++){
    for(i=(0);i<(N);i++){
      j = go[k-1][i];
      if(j==N){
        go[k][i] = N;
        continue;
      }
      go[k][i] = go[k-1][j];
      gos[k][i] = gos[k-1][j] + gos[k-1][i];
    }
  }
  for(k=(1);k<(20);k++){
    for(i=(0);i<(N);i++){
      j = bk[k-1][i];
      if(j==-1){
        bk[k][i] = -1;
        continue;
      }
      bk[k][i] = bk[k-1][j];
      bks[k][i] = bks[k-1][j] + bks[k-1][i];
    }
  }
  int ZIeRIny5 = rd_int();
  for(jbtyPBGc=(0);jbtyPBGc<(ZIeRIny5);jbtyPBGc++){
    rd(L);L += (-1);
    rd(R);R += (-1);
    mx = 0;
    k = L;
    s1 = L;
    for(i=19;i>=0;i--){
      if(go[i][k] <= R){
        s1 += gos[i][k];
        k = go[i][k];
        mx += (1<<i);
      }
    }
    k = R;
    s2 = R;
    for(i=19;i>=0;i--){
      if(bk[i][k] >= L){
        s2 += bks[i][k];
        k = bk[i][k];
      }
    }
    wt_L(s2-s1+mx+1);
    wt_L('\n');
  }
  return 0;
}
// cLay varsion 20200920-1

// --- original code ---
// int N, K, X[2d5], L, R;
// int go[20][2d5]; ll gos[20][2d5];
// int bk[20][2d5]; ll bks[20][2d5];
// {
//   int i, j, k, mx;
//   ll s1, s2;
//   rd(N,K,X(N));
// 
//   j = 0;
//   rep(i,N){
//     while(j < N && X[j] < X[i]+K) j++;
//     go[0][i] = j;
//     gos[0][i] = j;
//   }
//   j = N-1;
//   rrep(i,N){
//     while(j >= 0 && X[j] > X[i]-K) j--;
//     bk[0][i] = j;
//     bks[0][i] = j;
//   }
// 
//   rep(k,1,20) rep(i,N){
//     j = go[k-1][i];
//     if(j==N) go[k][i] = N, continue;
//     go[k][i] = go[k-1][j];
//     gos[k][i] = gos[k-1][j] + gos[k-1][i];
//   }
// 
//   rep(k,1,20) rep(i,N){
//     j = bk[k-1][i];
//     if(j==-1) bk[k][i] = -1, continue;
//     bk[k][i] = bk[k-1][j];
//     bks[k][i] = bks[k-1][j] + bks[k-1][i];
//   }
// 
//   REP(rd_int()){
//     rd(L--,R--);
// 
//     mx = 0;
// 
//     k = L;
//     s1 = L;
//     for(i=19;i>=0;i--) if(go[i][k] <= R) s1 += gos[i][k], k = go[i][k], mx += (1<<i);
// 
//     k = R;
//     s2 = R;
//     for(i=19;i>=0;i--) if(bk[i][k] >= L) s2 += bks[i][k], k = bk[i][k];
// 
//     wt(s2-s1+mx+1);
//   }
// }