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;
long long tr[19][200010 * 2];
int buffer[2][200010 * 2], a[200010], p, mlen;
int nxt[200010];
char single[200010];
const long long zero = 1LL * 200010 * (200010 * 2) * (200010 * 2) +
                       1LL * 200010 * (200010 * 2) + 1;
bool cmp(int i, int j) { return a[abs(i)] < a[abs(j)]; }
void build(int n, int m) {
  int i, l, r, md, nid, sum, mn, lsum, rsum, lmn, rmn, lc, rc, lv = 0;
  bool final;
  for (i = 0; i < n - m; i++) {
    buffer[p][i * 2] = i;
    buffer[p][i * 2 + 1] = -(i + m);
  }
  sort(buffer[p], buffer[p] + (n - m) * 2, cmp);
  nxt[0] = n - m;
  while (1) {
    final = true;
    for (l = 0; l < n - m; l = r) {
      r = nxt[l];
      if (l + 1 == r) {
        single[l]++;
        if (buffer[p][l * 2] >= 0) {
          tr[lv][l * 2] =
              zero - 1LL * (200010 * 2) * (200010 * 2) - (200010 * 2);
          tr[lv][l * 2 + 1] = zero;
        } else {
          tr[lv][l * 2] = zero + 1LL * (200010 * 2) * (200010 * 2);
          tr[lv][l * 2 + 1] = zero;
        }
        continue;
      }
      final = false;
      md = (l + r) / 2;
      nxt[l] = md;
      nxt[md] = r;
      lc = l * 2;
      rc = md * 2;
      for (i = l * 2; i < r * 2; i++) {
        if (buffer[p][i] >= 0) {
          nid = buffer[p][i];
        } else {
          nid = -buffer[p][i] - m;
        }
        if (nid < md) {
          buffer[p ^ 1][lc++] = buffer[p][i];
        } else {
          buffer[p ^ 1][rc++] = buffer[p][i];
        }
        tr[lv][i] = zero + lc - 1;
      }
    }
    if (final) break;
    p ^= 1;
    lv++;
  }
  lv--;
  while (lv >= 0) {
    for (l = 0; l < n - m; l = nxt[l]) {
      if (single[l] > 1) {
        single[l]--;
        continue;
      }
      md = nxt[l];
      nxt[l] = r = nxt[md];
      if (l + 1 == r) {
        continue;
      }
      for (i = l * 2; i < r * 2; i++) {
        lc = tr[lv][i] % (200010 * 2) - 1;
        rc = md * 2 + (i - lc) - 1;
        if (lc < l * 2) {
          lsum = lmn = 0;
        } else {
          lsum = tr[lv + 1][lc] / (200010 * 2) / (200010 * 2) - 200010;
          lmn = tr[lv + 1][lc] / (200010 * 2) % (200010 * 2) - 200010;
        }
        if (i == lc) {
          rsum = rmn = 0;
        } else {
          rsum = tr[lv + 1][rc] / (200010 * 2) / (200010 * 2) - 200010;
          rmn = tr[lv + 1][rc] / (200010 * 2) % (200010 * 2) - 200010;
        }
        sum = lsum + rsum;
        mn = min(lsum + rmn, lmn);
        tr[lv][i] +=
            1LL * sum * (200010 * 2) * (200010 * 2) + 1LL * mn * (200010 * 2);
      }
    }
    lv--;
  }
  memcpy(buffer[0], a, sizeof(int) * m);
  sort(buffer[0], buffer[0] + m);
  memcpy(buffer[1], a, sizeof(int) * (n - m));
  memcpy(buffer[1] + n - m, a + m, sizeof(int) * (n - m));
  sort(buffer[1], buffer[1] + (n - m) * 2);
}
int qpsum(int lv, int l, int r, int qr, int i) {
  if (i < l * 2) return 0;
  if (qr == r) return tr[lv][i] / (200010 * 2) / (200010 * 2) - 200010;
  int md = (l + r) / 2, lc = tr[lv][i] % (200010 * 2) - 1,
      rc = md * 2 + i - lc - 1;
  if (qr <= md)
    return qpsum(lv + 1, l, md, qr, lc);
  else
    return qpsum(lv + 1, l, md, md, lc) + qpsum(lv + 1, md, r, qr, rc);
}
long long qry(int lv, int l, int r, int ql, int qr, int i) {
  if (i < l * 2) return zero / (200010 * 2);
  if (l == ql && r == qr) {
    return tr[lv][i] / (200010 * 2);
  }
  int md = (l + r) / 2, lc = tr[lv][i] % (200010 * 2) - 1,
      rc = md * 2 + i - lc - 1;
  if (qr <= md) {
    return qry(lv + 1, l, md, ql, qr, lc);
  } else if (ql >= md) {
    return qry(lv + 1, md, r, ql, qr, rc);
  } else {
    long long lres = qry(lv + 1, l, md, ql, md, lc);
    long long rres = qry(lv + 1, md, r, md, qr, rc);
    return (lres / (200010 * 2) + rres / (200010 * 2) - 200010) * (200010 * 2) +
           min(lres % (200010 * 2),
               lres / (200010 * 2) + rres % (200010 * 2) - 200010);
  }
}
int cal(int l, int r, int n, int m, int q) {
  l--;
  r--;
  int base = lower_bound(buffer[0], buffer[0] + m, q) - buffer[0];
  int i =
      (upper_bound(buffer[1], buffer[1] + (n - m) * 2, q - 1) - buffer[1]) - 1;
  return base + (l ? qpsum(0, 0, n - m, l, i) : 0) +
         (l < r ? qry(0, 0, n - m, l, r, i) % (200010 * 2) - 200010 : 0);
}
int main() {
  int n, m, q, ans = 0, l, r, x, i;
  scanf("%d%d", &n, &m);
  for (i = 0; i < n; i++) scanf("%d", &a[i]);
  build(n, m);
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d%d", &l, &r, &x);
    x ^= ans;
    ans = cal(l, r, n, m, x);
    printf("%d\n", ans);
  }
  return 0;
}