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>
using namespace std;

#define Gene template< class
#define Rics printer& operator,
Gene c> struct rge{c b, e;};
Gene c> rge<c> range(c i, c j){ return {i, j};}
struct printer{
    ~printer(){cerr<<endl;}
    Gene c >Rics(c x){ cerr<<boolalpha<<x; return *this;}
    Rics(string x){cerr<<x;return *this;}
    Gene c, class d >Rics(pair<c, d> x){ return *this,"(",x.first,", ",x.second,")";}
    Gene ... d, Gene ...> class c >Rics(c<d...> x){ return *this, range(begin(x), end(x));}
    Gene c >Rics(rge<c> x){
        *this,"["; for(auto it = x.b; it != x.e; ++it)
            *this,(it==x.b?"":", "),*it; return *this,"]";}
};
#define debug() cerr<<"LINE "<<__LINE__<<" >> ", printer()
#define dbg(x) "[",#x,": ",(x),"] "
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int my_rand(int l, int r) {
    return uniform_int_distribution<int>(l, r) (rng);
}

const int N = 2e5+100;
const int LOG = 20;

int a[N];
int nxt[N][LOG], prv[N][LOG];
long long nxt_sum[N][LOG], prv_sum[N][LOG];

int main() {
//    freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, K;
    cin >> n >> K;
    for(int i = 1; i <= n; i++) cin >> a[i];

    for(int i = 1; i <= n; i++) {
        if(a[n]-a[i] < K) nxt[i][0] = -1;
        else {
            int lo = i+1, hi = n;
            while(hi > lo) {
                int mid = lo+hi>>1;
                if(a[mid]-a[i] >= K) hi = mid;
                else lo = mid+1;
            }
            nxt[i][0] = lo;
        }
        nxt_sum[i][0] = i;
    }
    for(int i = 1; i <= n; i++) {
        if(a[i]-a[1] < K) prv[i][0] = -1;
        else {
            int lo = 1, hi = i-1;
            while(hi > lo) {
                int mid = (lo+hi+1)>>1;
                if(a[i]-a[mid] >= K) lo = mid;
                else hi = mid-1;
            }
            prv[i][0] = lo;
        }
        prv_sum[i][0] = i;
    }

    for(int k = 1; k < LOG; k++) {
        for(int i = 1; i <= n; i++) {
            if(nxt[i][k-1] == -1) nxt[i][k] = -1;
            else {
                nxt[i][k] = nxt[nxt[i][k-1]][k-1];
                nxt_sum[i][k] = nxt_sum[i][k-1] + nxt_sum[nxt[i][k-1]][k-1];
            }

            if(prv[i][k-1] == -1) prv[i][k] = -1;
            else {
                prv[i][k] = prv[prv[i][k-1]][k-1];
                prv_sum[i][k] = prv_sum[i][k-1] + prv_sum[prv[i][k-1]][k-1];
            }
        }
    }
    int q;
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r;
        int m = 1;
        int cur = l;
        for(int k = LOG-1; k >= 0; k--) {
            if(nxt[cur][k] != -1 && nxt[cur][k] <= r) {
                cur = nxt[cur][k];
                m += (1<<k);
            }
        }
        int curl = l, curr = r;
        long long lsum = 0, rsum = 0;
        for(int k = LOG-1; k >= 0; k--) {
            if((m >> k) & 1) {
                lsum += nxt_sum[curl][k];
                rsum += prv_sum[curr][k];
                curl = nxt[curl][k];
                curr = prv[curr][k];
            }
        }
        long long ans = rsum - lsum + m;
        cout << ans << "\n";
    }
}