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>
#pragma GCC optimize(2)
using namespace std;
void qread(int &x) {
  int neg = 1;
  x = 0;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') neg = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = 10 * x + c - '0', c = getchar();
  x *= neg;
}
const int maxn = 200005;
const int bit = 9;
const int maxm = (1 << bit) - 1;
const int maxs = (maxn + maxm - 1) / maxm;
int n, m, q, last;
pair<int, int> a[maxn];
int mn[maxs][maxs], mn2[maxs][maxs];
int tag[maxs], val[maxn], from[maxn], to[maxn], bfrom[maxn], bto[maxn], ind[2],
    bmn[2];
class Data {
 public:
  int t, pos, val;
  Data(int _t = 0, int _pos = 0, int _val = 0) : t(_t), pos(_pos), val(_val) {}
  bool operator<(const Data &o) const {
    if (t != o.t) return t < o.t;
    return pos < o.pos;
  }
};
vector<Data> upd[maxs];
vector<vector<int> > st[maxs];
int calc(int i) {
  int res = 1e9;
  for (int j = i << bit; j < min(n - m + 1, (i + 1) << bit); j++)
    res = min(res, tag[i] + val[j]);
  return res;
}
void add(int i) {
  from[i] = max(0, a[i].second - m + 1), to[i] = min(a[i].second, n - m);
  if (!(i & maxm)) {
    int cur = i >> bit;
    for (int(j) = 0; (j) < maxs; j++) {
      mn[cur][j] = mn2[cur][j] = 1e9;
      for (int k = j << bit; k < min((j + 1) << bit, n - m + 1); k++) {
        mn[cur][j] = min(mn[cur][j], tag[j] + val[k]);
      }
      mn2[cur][j] = tag[j];
    }
  }
  if (i == n) return;
  int l = (from[i] >> bit), r = (to[i] >> bit);
  bmn[0] = calc(l);
  bmn[1] = calc(r);
  for (int j = from[i]; j <= to[i];) {
    if (!(j & maxm) && j + maxm <= to[i])
      tag[j >> bit]++, j += (1 << bit);
    else
      val[j]++, j++;
  }
  bfrom[i] = l;
  bto[i] = r;
  if (calc(l) == bmn[0]) bfrom[i]++;
  if (calc(r) == bmn[1]) bto[i]--;
  if ((from[i] & maxm) || to[i] - from[i] < maxm)
    upd[l].push_back(Data(i, from[i] & maxm, 1));
  if ((to[i] & maxm) != maxm || to[i] - from[i] < maxm) {
    if (l != r) upd[r].push_back(Data(i, 0, 1));
    upd[r].push_back(Data(i, (to[i] & maxm) + 1, -1));
  }
}
int qry(int tm, int from, int to) {
  int l = (from >> bit), r = (to >> bit), t = (tm >> bit), ans = 1e9;
  ind[0] = l;
  ind[1] = r;
  for (int(p) = 0; (p) < 2; p++) {
    if (p == 1 && ind[0] == ind[1]) continue;
    int cur = ind[p];
    vector<int> tmp;
    int pos = lower_bound(upd[cur].begin(), upd[cur].end(), Data(tm, -1, -1)) -
              upd[cur].begin();
    if ((pos >> bit) - 1 >= 0)
      tmp = st[cur][(pos >> bit) - 1];
    else
      tmp = vector<int>(maxm + 5);
    for (int j = (pos >> bit) << bit; j < pos; j++)
      tmp[upd[cur][j].pos] += upd[cur][j].val;
    int base = mn2[t][cur];
    for (int i = t << bit; i < tm; i++)
      if (::from[i] <= (cur << bit) && ::to[i] >= ((cur + 1) << bit) - 1)
        base++;
    for (int(i) = 0; (i) < maxm + 1; i++) {
      if (i) tmp[i] += tmp[i - 1];
      if ((cur << bit) + i >= from && (cur << bit) + i <= to)
        ans = min(ans, base + tmp[i]);
    }
  }
  vector<int> tmp(maxs + 5);
  for (int(i) = 0; (i) < maxs; i++) tmp[i] = mn[t][i];
  for (int i = maxs - 1; i >= 1; i--) tmp[i] -= tmp[i - 1];
  for (int i = t << bit; i < tm; i++)
    if (bfrom[i] <= bto[i]) {
      tmp[bfrom[i]]++;
      tmp[bto[i] + 1]--;
    }
  for (int(i) = 0; (i) < maxs; i++) {
    if (i) tmp[i] += tmp[i - 1];
    if (i > l && i < r) ans = min(ans, tmp[i]);
  }
  return ans;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int(i) = 0; (i) < n; i++) scanf("%d", &a[i].first), a[i].second = i;
  sort(a, a + n);
  for (int(i) = 0; (i) < n + 1; i++) add(i);
  for (int(i) = 0; (i) < maxs; i++) {
    vector<int> tmp(maxm + 5);
    for (int(j) = 0; (j) < upd[i].size(); j++) {
      tmp[upd[i][j].pos] += upd[i][j].val;
      if ((j & maxm) == maxm) st[i].push_back(tmp);
    }
  }
  scanf("%d", &q);
  while (q--) {
    int l, r, x;
    scanf("%d%d%d", &l, &r, &x);
    l--;
    r--;
    x ^= last;
    int pos = lower_bound(a, a + n, make_pair(x, -1)) - a;
    int ans = qry(pos, l, r);
    printf("%d\n", ans);
    last = ans;
  }
  return 0;
}