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 <bits/stdc++.h>
//#include <chrono>
//#pragma GCC optimize("Ofast")
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second

using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;

ll N,M,H,W,Q,K,A,B;
string S;
typedef pair<ll, ll> P;
const ll INF = (1LL<<60);

ll solve(int l, int r,mat &dv, mat &dvr, mat &dsum, mat &dsumr){
    ll res(r - l);
    int nowl(l), nowr(r), len(1);
    Rrep(i, 18){
        if(dv[i][nowl] <= r){
            res -= dsum[i][nowl];
            nowl = dv[i][nowl];
            len += 1<<i;
        }
        if(dvr[i][nowr] >= l){
            res += dsumr[i][nowr];
            nowr = dvr[i][nowr];
        }
    }
    return res + len;
}

int main() {
    cin>>N>>K;
    N += 2;
    vec x(N), x_rev(N);
    mat dbl(18, vec(N)), dbl_rev(18, vec(N)), dbl_sum(18, vec(N, 0)), dbl_rev_sum(18, vec(N, 0));
    reps(i, 1, N - 1) cin>>x[i];
    x[0] = -INF; x[N - 1] = INF;
    copy(x.rbegin(), x.rend(), x_rev.begin());
    rep(i, N) x_rev[i] = - x_rev[i];
    //reps(i, 1, N - 1) cout<<x_rev[i]<<" \n"[i == N - 2];
    rep(i, N) {
        dbl[0][i] = dbl_sum[0][i] = min(N - 1, (ll)(lower_bound(ALL(x), x[i] + K) - x.begin()));
        dbl_rev[0][i] = dbl_rev_sum[0][i] = N - 1 - min(N - 1, (ll)(lower_bound(ALL(x_rev), x_rev[N - 1 - i] + K) - x_rev.begin()));
        //cout<<dbl_rev[0][i]<<" \n"[i == N - 1];
    }
    reps(i, 1, 18) {
        rep(v, N) {
            dbl[i][v] = dbl[i-1][dbl[i-1][v]];
            dbl_rev[i][v] = dbl_rev[i-1][dbl_rev[i-1][v]];
            dbl_sum[i][v] = dbl_sum[i-1][v] + dbl_sum[i-1][dbl[i-1][v]];
            dbl_rev_sum[i][v] = dbl_rev_sum[i-1][v] + dbl_rev_sum[i-1][dbl_rev[i-1][v]];
        }
    }
    cin>>Q;
    rep(_, Q){
        int l, r; cin>>l>>r;
        cout<<solve(l, r, dbl, dbl_rev, dbl_sum, dbl_rev_sum)<<endl;
    }
}