Problem: Please note that the memory limit differs from the standard.

You really love to listen to music. During the each of next s days you will listen to exactly m songs from the playlist that consists of exactly n songs. Let's number the songs from the playlist with numbers from 1 to n, inclusive. The quality of song number i is ai.

On the i-th day you choose some integer v (li ≤ v ≤ ri) and listen to songs number v, v + 1, ..., v + m - 1. On the i-th day listening to one song with quality less than qi increases your displeasure by exactly one.

Determine what minimum displeasure you can get on each of the s next days. 

Input

The first line contains two positive integers n, m (1 ≤ m ≤ n ≤ 2·105). The second line contains n positive integers a1, a2, ..., an (0 ≤ ai < 230) — the description of songs from the playlist. 

The next line contains a single number s (1 ≤ s ≤ 2·105) — the number of days that you consider.

The next s lines contain three integers each li, ri, xi (1 ≤ li ≤ ri ≤ n - m + 1; 0 ≤ xi < 230) — the description of the parameters for the i-th day. In order to calculate value qi, you need to use formula: <image>, where ansi is the answer to the problem for day i. Assume that ans0 = 0. 

Output

Print exactly s integers ans1, ans2, ..., anss, where ansi is the minimum displeasure that you can get on day i.

Examples

Input

5 3
1 2 1 2 3
5
1 1 2
1 3 2
1 3 3
1 3 5
1 3 1


Output

2
0
2
3
1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vb = vector<bool>;
using vs = vector<string>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  const int UPD_GROUP_SIZE = 500;
  const int ELT_GROUP_SIZE = 500;
  int N, M;
  cin >> N >> M;
  const int UPD_GROUP_CT = N / UPD_GROUP_SIZE + 1;
  const int ELT_GROUP_CT = (N + ELT_GROUP_SIZE - 1) / ELT_GROUP_SIZE;
  vi qual(N);
  for (int i = 0; i < N; i++) {
    cin >> qual[i];
  }
  vi order(N);
  for (int i = 0; i < N; i++) {
    order[i] = i;
  }
  sort((order).begin(), (order).end(),
       [&](int i, int j) { return qual[i] > qual[j]; });
  vi ordered_qual = qual;
  sort((ordered_qual).begin(), (ordered_qual).end(), greater<int>());
  vvi init(UPD_GROUP_CT, vi(ELT_GROUP_CT));
  vvi maxv(UPD_GROUP_CT, vi(ELT_GROUP_CT));
  vector<array<int, 2>> iupd(N);
  vector<array<int, 2>> mupd(N);
  vi diff(N + 1);
  for (int _i = 0; _i <= N; _i++) {
    if (_i % UPD_GROUP_SIZE == 0) {
      const int GROUP = _i / UPD_GROUP_SIZE;
      vi curv(N);
      for (int i = 0; i < N; i++) {
        curv[i] = diff[i] + (i ? curv[i - 1] : 0);
        int BUCKET = i / ELT_GROUP_SIZE;
        if (i % ELT_GROUP_SIZE == 0) {
          init[GROUP][BUCKET] = curv[i];
        }
        maxv[GROUP][BUCKET] = max(curv[i], maxv[GROUP][BUCKET]);
      }
      for (int ops = 0; ops < UPD_GROUP_SIZE; ops++) {
        int _j = _i + ops;
        if (_j >= N) {
          break;
        }
        int r = order[_j];
        int l = max(0, r - M + 1);
        iupd[_j] = {(l + ELT_GROUP_SIZE - 1) / ELT_GROUP_SIZE,
                    r / ELT_GROUP_SIZE};
        auto incr_max = [&](int bl, int br) {
          int cmax = 0, nmax = 0;
          for (int i = bl; i <= br; i++) {
            if (i < N) cmax = max(cmax, curv[i]);
            if (l <= i && i <= r) {
              curv[i]++;
            }
            if (i < N) nmax = max(nmax, curv[i]);
          }
          return nmax > cmax;
        };
        mupd[_j] = {INT_MAX, -1};
        for (int b = 0; b < ELT_GROUP_CT; b++) {
          int bl = b * ELT_GROUP_SIZE;
          int br = bl + ELT_GROUP_SIZE - 1;
          int il = max(l, bl), ir = min(r, br);
          bool minc = false;
          if (il == bl && ir == br) {
            minc = true;
          } else if (il <= ir) {
            minc = incr_max(bl, br);
          }
          if (minc) {
            mupd[_j][0] = min(mupd[_j][0], b);
            mupd[_j][1] = max(mupd[_j][1], b);
          }
        }
      }
    }
    if (_i < N) {
      int r = order[_i];
      int l = max(0, r - M + 1);
      diff[l]++;
      diff[r + 1]--;
    }
  }
  int S, ans = 0;
  cin >> S;
  for (int d = 0; d < S; d++) {
    int l, r, x;
    cin >> l >> r >> x;
    l--, r--;
    x ^= ans;
    ;
    int LIM = upper_bound((ordered_qual).begin(), (ordered_qual).end(), x,
                          greater<int>()) -
              ordered_qual.begin();
    ;
    const int UPD_BASE_GROUP = LIM / UPD_GROUP_SIZE;
    vi spec_init = init[UPD_BASE_GROUP];
    vi spec_maxv = maxv[UPD_BASE_GROUP];
    vi diff_init(ELT_GROUP_CT + 1), diff_maxv(ELT_GROUP_CT + 1);
    for (int _i = UPD_BASE_GROUP * UPD_GROUP_SIZE; _i < LIM; _i++) {
      if (iupd[_i][0] <= iupd[_i][1]) {
        diff_init[iupd[_i][0]]++;
        diff_init[iupd[_i][1] + 1]--;
      }
      if (mupd[_i][0] <= mupd[_i][1]) {
        diff_maxv[mupd[_i][0]]++;
        diff_maxv[mupd[_i][1] + 1]--;
      }
    }
    int cur_diff_init = 0, cur_diff_maxv = 0;
    for (int b = 0; b < ELT_GROUP_CT; b++) {
      cur_diff_init += diff_init[b];
      cur_diff_maxv += diff_maxv[b];
      spec_init[b] += cur_diff_init;
      spec_maxv[b] += cur_diff_maxv;
    };
    ;
    int res = 0;
    for (int b = 0; b < ELT_GROUP_CT; b++) {
      int bl = b * ELT_GROUP_SIZE, br = bl + ELT_GROUP_SIZE - 1;
      if (l <= bl && br <= r) {
        res = max(res, spec_maxv[b]);
        if (res > M) {
        }
      } else if (max(l, bl) <= min(r, br)) {
        int val = spec_init[b];
        for (int i = bl; i <= br; i++) {
          if (l <= i && i <= r) res = max(res, val);
          if (i < N && qual[i] >= x) val--;
          if (i + M < N && qual[i + M] >= x) val++;
        }
      }
    }
    ans = M - res;
    cout << ans << "\n";
  }
  return 0;
}