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;
int n, m, a[222222], b[222222], c[222222];
int ib[222222], bl[1111], br[1111], mn[1111][1111], st[1111][1111], w[222222],
    ad[1111], cnt;
int pre[222222], suf[222222], q, l, r, x, ans, W[1111], bt, ls, rs, lp, rp;
const int magic = 444;
bool cmp(int i, int j) { return a[i] < a[j]; }
void update(int k, int l, int r) {
  pre[k] = suf[k] = 1e9;
  if (ib[l] == ib[r]) {
    for (int i = l; i <= r; i++) w[i]++;
    for (int i = bl[ib[l]]; i <= br[ib[l]]; i++) pre[k] = min(pre[k], w[i]);
    return;
  }
  int il = ib[l], ir = ib[r];
  for (int i = il + 1; i < ir; i++) ad[i]++;
  for (int i = l; i <= br[il]; i++) w[i]++;
  for (int i = bl[il]; i <= br[il]; i++) pre[k] = min(pre[k], w[i]);
  for (int i = bl[ir]; i <= r; i++) w[i]++;
  for (int i = bl[ir]; i <= br[ir]; i++) suf[k] = min(suf[k], w[i]);
}
void restore(int x) {
  for (int i = 1; i <= n; i++) {
    w[i] += ad[ib[i]];
  }
  memset(ad, 0, sizeof(ad));
  for (int i = 1; i <= cnt; i++) mn[x][i] = 1e9;
  for (int i = 1; i <= n; i++) {
    if (ib[i] != ib[i - 1]) st[x][ib[i]] = w[i];
    mn[x][ib[i]] = min(mn[x][ib[i]], w[i]);
  }
}
int query(int l, int r, int id, int s, int x) {
  int now = s, ans = 1e9;
  for (int i = bl[id]; i < l; i++) now += ((a[i + m] < x) - (a[i] < x));
  for (int i = l; i <= r; i++) {
    ans = min(ans, now);
    now += ((a[i + m] < x) - (a[i] < x));
  }
  return ans;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) b[i] = i;
  sort(b + 1, b + n + 1, cmp);
  for (int i = 1; i <= n; i++) c[i] = a[b[i]];
  for (int i = 1; i <= n; i++) {
    if ((i - 1) * magic + 1 > n) break;
    bl[i] = (i - 1) * magic + 1;
    br[i] = min(n, i * magic);
    for (int j = bl[i]; j <= br[i]; j++) ib[j] = i;
  }
  cnt = ib[n];
  for (int i = 1; i <= n; i++) {
    update(i, max(1, b[i] - m + 1), b[i]);
    if (ib[i] != ib[i + 1]) restore(ib[i]);
  }
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d%d", &l, &r, &x);
    x ^= ans;
    int pos = lower_bound(c + 1, c + n + 1, x) - c;
    if (pos > n || c[pos] >= x) pos--;
    memset(ad, 0, sizeof(ad));
    bt = ib[pos];
    for (int i = 1; i <= cnt; i++) {
      W[i] = mn[bt - 1][i];
    }
    lp = bl[ib[l]];
    rp = bl[ib[r]];
    ls = st[bt - 1][ib[l]];
    rs = st[bt - 1][ib[r]];
    for (int i = bl[bt]; i <= br[bt] && i <= pos; i++) {
      int L = max(1, b[i] - m + 1), R = b[i], il = ib[L], ir = ib[R];
      if (il == ir) {
        W[il] = pre[i];
      } else {
        W[il] = pre[i];
        W[ir] = suf[i];
        ad[il + 1]++;
        ad[ir]--;
      }
      if (L <= lp && lp <= R) ls++;
      if (L <= rp && rp <= R) rs++;
    }
    for (int i = 1; i <= cnt; i++) ad[i] += ad[i - 1];
    if (ib[l] == ib[r]) {
      ans = query(l, r, ib[l], ls, x);
    } else {
      ans = min(query(l, br[ib[l]], ib[l], ls, x),
                query(bl[ib[r]], r, ib[r], rs, x));
      for (int i = ib[l] + 1; i < ib[r]; i++) ans = min(ans, W[i] + ad[i]);
    }
    printf("%d\n", ans);
  }
  return 0;
}