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 BS = 1 << 9;
const int MAX = 1 << 18;
int dat[MAX] = {};
int val[MAX / BS] = {};
int add[MAX / BS] = {};
int frt[MAX / BS] = {};
int bf[MAX / BS][MAX / BS];
int bm[MAX / BS][MAX / BS];
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 / BS) * BS;
    if (add[l / BS] == 0) return;
    for (int j = l; j < l + BS; j++) dat[j] += add[j / BS];
    add[l / BS] = 0;
  };
  memset(cp, -1, sizeof(cp));
  for (int i = 0; i < n; i++) {
    if (i % BS == 0) {
      for (int j = 0; j < MAX; j += BS) {
        val[j / BS] += add[j / BS];
        eval(j);
        bf[i / BS][j / BS] = dat[j];
        bm[i / BS][j / BS] = val[j / BS];
      }
    }
    int r = vp[i].second + 1;
    int l = max(0, r - m);
    int idx = 0;
    for (int j = l; j < r; j++) {
      if (j % BS == 0 && j + BS <= r) {
        add[j / BS] += 1;
        j += BS - 1;
      } else {
        dat[j] += 1;
        chmax(val[j / BS], dat[j]);
        if (cp[idx][i] != j / BS) {
          idx++;
          cp[idx][i] = j / BS;
        }
        cv[idx][i] = val[j / BS];
      }
    }
    while (idx < 2) {
      idx++;
      cp[idx][i] = MAX / BS - 1;
      cv[idx][i] = 0;
    }
  }
  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 / BS * BS;
    for (int j = 0; j < MAX; j += BS) {
      val[j / BS] = bm[k / BS][j / BS];
      add[j / BS] = 0;
      frt[j / BS] = bf[k / BS][j / BS];
    }
    for (int i = k; i < idx; i++) {
      int q = vp[i].second + 1;
      int p = max(0, q - m);
      if (p % BS) p = (p / BS + 1) * BS;
      if (p <= q) {
        add[p / BS] += 1;
        add[q / BS] -= 1;
      }
      val[cp[1][i]] = cv[1][i];
      val[cp[2][i]] = cv[2][i];
      if (p <= q && q % BS) frt[q / BS] += 1;
    }
    for (int j = BS; j < MAX; j += BS) add[j / BS] += add[j / BS - 1];
    int res = 0, flg = 0, tmp = 0;
    for (int j = l; j < r; j++) {
      if (j % BS == 0 && j + BS <= r) {
        chmax(res, val[j / BS] + add[j / BS]);
        j += BS - 1;
        flg = 0;
      } else {
        if (flg == 0) {
          flg = 1;
          tmp = frt[j / BS] + add[j / BS];
          int p = j / BS * BS;
          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;
}