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 Int = long long;
template <typename T1, typename T2>
inline void chmin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
inline void chmax(T1 &a, T2 b) {
  if (a < b) a = b;
}
const int X = 9;
const int BS = 1 << X;
const int MAX = 1 << 18;
int dat[MAX] = {};
int val[MAX >> X] = {};
int add[MAX >> X] = {};
int frt[MAX >> X] = {};
int bf[MAX >> X][MAX >> X];
int bm[MAX >> X][MAX >> X];
int cp[3][MAX] = {};
int cv[3][MAX] = {};
signed main() {
  int n, m;
  cin >> n >> m;
  vector<int> as(n + n, 0);
  for (int i = 0; i < n; i++) cin >> as[i];
  using P = pair<int, int>;
  vector<P> vp;
  for (int i = 0; i < n; i++) vp.emplace_back(-as[i], i);
  sort(vp.begin(), vp.end());
  auto eval = [&](int i) {
    int l = (i >> X) << X;
    if (add[l >> X] == 0) return;
    for (int j = l; j < l + BS; j++) dat[j] += add[j >> X];
    add[l >> X] = 0;
  };
  for (int i = 0; i < n; i++) {
    if ((i & (BS - 1)) == 0) {
      for (int j = 0; j < MAX; j += BS) {
        val[j >> X] += add[j >> X];
        eval(j);
        bf[i >> X][j >> X] = dat[j];
        bm[i >> X][j >> X] = val[j >> X];
      }
    }
    int r = vp[i].second + 1;
    int l = max(0, r - m);
    int idx = 0;
    cp[idx][i] = -1;
    for (int j = l; j < r; j++) {
      if ((j & (BS - 1)) == 0 && j + BS <= r) {
        add[j >> X] += 1;
        j += BS - 1;
      } else {
        dat[j] += 1;
        chmax(val[j >> X], dat[j]);
        if (cp[idx][i] != j >> X) {
          idx++;
          cp[idx][i] = j >> X;
        }
        cv[idx][i] = val[cp[idx][i]];
      }
    }
    while (idx < 2) {
      idx++;
      cp[idx][i] = (MAX >> X) - 1;
      cv[idx][i] = val[cp[idx][i]];
    }
  }
  auto calc = [&](int l, int r, int v) -> int {
    int idx = upper_bound(vp.begin(), vp.end(), P(-v, n)) - vp.begin();
    int k = (idx >> X) << X;
    for (int j = 0; j < MAX; j += BS) {
      val[j >> X] = bm[k >> X][j >> X];
      add[j >> X] = 0;
      frt[j >> X] = bf[k >> X][j >> X];
    }
    for (int i = k; i < idx; i++) {
      int q = vp[i].second + 1;
      int p = max(0, q - m);
      if (p & (BS - 1)) p = ((p >> X) + 1) << X;
      if (p <= q) {
        add[p >> X] += 1;
        add[q >> X] -= 1;
      }
      val[cp[1][i]] = cv[1][i];
      val[cp[2][i]] = cv[2][i];
      if (p <= q && (q & (BS - 1))) frt[q >> X] += 1;
    }
    for (int j = BS; j < MAX; j += BS) add[j >> X] += add[(j >> X) - 1];
    int res = 0, flg = 0, tmp = 0;
    for (int j = l; j < r; j++) {
      if ((j & (BS - 1)) == 0 && j + BS <= r) {
        chmax(res, val[j >> X] + add[j >> X]);
        j += BS - 1;
        flg = 0;
      } else {
        if (flg == 0) {
          flg = 1;
          tmp = frt[j >> X] + add[j >> X];
          int p = (j >> X) << X;
          while (p < j) {
            tmp -= as[p] >= v;
            tmp += as[p + m] >= v;
            p++;
          }
        }
        chmax(res, tmp);
        tmp -= as[j] >= v;
        tmp += as[j + m] >= v;
      }
    }
    return m - res;
  };
  int q;
  cin >> q;
  int pre_ans = 0;
  for (int i = 0; i < q; i++) {
    int l, r, x;
    cin >> l >> r >> x;
    l--;
    int ans = calc(l, r, x ^ pre_ans);
    cout << ans << "\n";
    pre_ans = ans;
  }
  cout << flush;
  return 0;
}