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;
const int inf = 1e9;
const int bound = 400;
struct qq {
  int id, vl;
  bool operator<(const qq &temp) const { return vl < temp.vl; }
};
qq bk[210000 / bound][bound], ns;
int nk[210000 / bound];
struct pp {
  int vl, id, min_value, value;
  int flag;
  bool operator<(const pp &temp) const { return vl < temp.vl; }
};
pp bl[210000 / bound][2 * bound], now;
int num[210000 / bound], num_bl, cnt_list, np[2 * bound];
int m, n, a[220000], num_q, ans, nw;
int lower_bound(int left, int right, qq bl[], int x) {
  int mid;
  while (left <= right) {
    mid = (left + right) >> 1;
    if (bl[mid].vl < x)
      left = mid + 1;
    else
      right = mid - 1;
  }
  return right;
}
int lower_bound(int left, int right, pp bl[], int x) {
  int mid;
  while (left <= right) {
    mid = (left + right) >> 1;
    if (bl[mid].vl < x)
      left = mid + 1;
    else
      right = mid - 1;
  }
  return right;
}
int main() {
  int i, j, s, p, q, ip, id, l, r, x, fir;
  scanf("%d%d", &n, &m);
  for (i = 0; i < n; i++) scanf("%d", &a[i]);
  memset(num, 0, sizeof(num));
  memset(nk, 0, sizeof(nk));
  num_bl = 0;
  for (i = 0; i < n; i++) {
    if (i % bound == 0) {
      for (j = i; j < min(n, i + bound); j++) {
        if (j + m < n) {
          now.id = j;
          now.vl = a[j];
          now.flag = -1;
          bl[num_bl][num[num_bl]++] = now;
          now.id = j + m;
          now.vl = a[j + m];
          now.flag = 1;
          bl[num_bl][num[num_bl]++] = now;
        }
        ns.id = j;
        ns.vl = a[j];
        bk[num_bl][nk[num_bl]++] = ns;
      }
      num_bl++;
    }
  }
  for (i = 0; i < num_bl; i++) {
    sort(bl[i], bl[i] + num[i]);
    sort(bk[i], bk[i] + nk[i]);
    for (j = i * bound; j < min((i + 1) * bound, n); j++) np[j - i * bound] = 0;
    for (j = 0; j < num[i]; j++) {
      bl[i][j].value = bl[i][j].flag;
      ip = bl[i][j].id;
      if (bl[i][j].flag > 0) ip -= m;
      np[ip - i * bound] += bl[i][j].flag;
      if (bl[i][j].flag < 0) {
        if (bl[i][j].id + m >= n) {
          bl[i][j].value = 0;
          np[ip - i * bound]++;
        }
      }
      if (j) {
        bl[i][j].value += bl[i][j - 1].value;
      }
      bl[i][j].min_value = 0;
      nw = 0;
      for (s = i * bound; s < min((i + 1) * bound, n); s++) {
        nw += np[s - i * bound];
        if (bl[i][j].min_value > nw) bl[i][j].min_value = nw;
      }
    }
  }
  scanf("%d", &num_q);
  ans = 0;
  while (num_q--) {
    scanf("%d%d%d", &l, &r, &x);
    l--;
    r--;
    x ^= ans;
    ans = 0;
    id = l / bound;
    nw = fir = 0;
    for (i = l; i <= min(l + m - 1, (l / bound + 1) * bound - 1); i++) {
      if (a[i] < x) fir++;
    }
    if (l + m - 1 >= (l / bound + 1) * bound) {
      for (i = (l + m - 1) / bound * bound; i <= l + m - 1; i++) {
        if (a[i] < x) fir++;
      }
      for (i = l / bound + 1; i < (l + m - 1) / bound; i++) {
        id = lower_bound(0, nk[i] - 1, bk[i], x);
        fir += (id + 1);
      }
    }
    for (i = l; i <= min(r - 1, (l / bound + 1) * bound - 1); i++) {
      if (i + m < n) {
        if (a[i] < x) nw--;
        if (a[i + m] < x) nw++;
        if (ans > nw) ans = nw;
      }
    }
    if (r - 1 >= (l / bound + 1) * bound) {
      for (i = l / bound + 1; i < (r - 1) / bound; i++) {
        id = lower_bound(0, num[i] - 1, bl[i], x);
        if (id >= 0) {
          if (nw + bl[i][id].min_value < ans) ans = nw + bl[i][id].min_value;
          nw += bl[i][id].value;
        }
      }
      for (i = ((r - 1) / bound) * bound; i <= r - 1; i++) {
        if (i + m < n) {
          if (a[i] < x) nw--;
          if (a[i + m] < x) nw++;
          if (ans > nw) ans = nw;
        }
      }
    }
    ans += fir;
    printf("%d\n", ans);
  }
  return 0;
}