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:
const long long MOD = 1e9 + 7;
const long long INF = 1e9;
const long long INFLL = 1e18;

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef complex<double> cd;

#define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define fi first
#define se second
#define re return
#define pb push_back
#define uniq(x) sort(all(x)); (x).resize(unique(all(x)) - (x).begin())

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
#define ln cerr << __LINE__ << endl
#else
#define dbg(x) void(0)
#define ln void(0)
#endif // LOCAL

const int N = 200000;

int canL[N], canR[N];

signed main()
{
    srand(time(NULL));
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    ll n, k;
    cin >> n >> k;
    vector<int> x(n + 1);
    forn(i, n) cin >> x[i + 1];
    vector<vector<ll> > goR(20, vector<ll>(n + 2));
    vector<vector<ll> > goL(20, vector<ll>(n + 2));
    vector<vector<ll> > summR(20, vector<ll>(n + 2));
    vector<vector<ll> > summL(20, vector<ll>(n + 2));
    for (int i = 1, j = 1; i <= n; i++)
    {
        while (j <= n && x[j] - x[i] < k)
        {
            j++;
        }
        goR[0][i] = j;
    }
    goR[0][0] = 1;
    goR[0][n + 1] = n + 1;
    summR[0] = goR[0];
    for (int i = n, j = n; i >= 1; i--)
    {
        while (j >= 1 && x[i] - x[j] < k)
        {
            j--;
        }
        goL[0][i] = j;
    }
    goL[0][0] = 0;
    goL[0][n + 1] = n;
    summL[0] = goL[0];
    for (int j = 1; j < 20; j++)
    {
        for (int i = 0; i <= n + 1; i++)
        {
            goR[j][i] = goR[j - 1][goR[j - 1][i]];
            goL[j][i] = goL[j - 1][goL[j - 1][i]];
            summR[j][i] = summR[j - 1][i] + summR[j - 1][goR[j - 1][i]];
            summL[j][i] = summL[j - 1][i] + summL[j - 1][goL[j - 1][i]];
        }
    }
    int q;
    cin >> q;
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        int sz = 1;
        int w = l;
        for (int j = 19; j >= 0; j--)
        {
            int nxt = goR[j][w];
            if (nxt <= r)
            {
                w = nxt;
                sz += (1 << j);
            }
        }
        ll ans = 0;
        {
            ll w = r;
            ll si = r;
            for (int j = 19; j >= 0; j--)
            {
                ll go = goL[j][w];
                if (l <= go)
                {
                    si += summL[j][w];
                    w = go;
                }
            }
            ans += si;
        }
        {
            ll w = l;
            ll si = l;
            for (int j = 19; j >= 0; j--)
            {
                ll go = goR[j][w];
                if (go <= r)
                {
                    si += summR[j][w];
                    w = go;
                }
            }
            ans -= si;
        }
        cout << sz + ans << "\n";
    }
}

/* Note:
Check constants at the beginning of the code (MOD, INF, INFLL)
Check corner cases.
    N = 1
No def int long long for now.
Add something here.
*/