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, q, a[200005], b[200005], be[200005], en[200005],
    d[200005 / 455 + 5][200005 / 455 + 5],
    mn[200005 / 455 + 5][200005 / 455 + 5],
    fr[200005 / 455 + 5][200005 / 455 + 5], val[200005], D[200005 / 455 + 5],
    Mn[200005 / 455 + 5], Fr[200005 / 455 + 5], md[200005][2], ans;
bool cmp(int x, int y) { return a[x] < a[y]; }
int find(int x) {
  int l = 0, r = n + 1, mid;
  while (r - l > 1) {
    mid = (l + r) >> 1;
    if (a[b[mid]] <= x)
      l = mid;
    else
      r = mid;
  }
  return l;
}
void solve(int l, int r, int x) {
  int i, sum, px, pl = l / 455, pr = r / 455, L, R, y = x;
  x = find(x - 1), px = x / 455;
  for (i = 0; i <= n / 455; i++) D[i] = Mn[i] = Fr[i] = 0;
  for (i = be[px]; i <= x; i++) {
    L = max(b[i] - m + 1, 1), R = b[i];
    Mn[L / 455] = md[i][0];
    Mn[R / 455] = md[i][1];
    if (L == be[L / 455]) Fr[L / 455]++;
    if (R / 455 != L / 455) D[L / 455 + 1]++, D[R / 455]--, Fr[R / 455]++;
  }
  for (i = 1; i <= n / 455; i++) D[i] += D[i - 1];
  if (px) {
    for (i = 0; i <= n / 455; i++) {
      D[i] += d[px - 1][i];
      if (!Mn[i]) Mn[i] = mn[px - 1][i];
      Fr[i] += fr[px - 1][i];
    }
  }
  ans = (1 << 30);
  sum = Fr[pl] + D[pl];
  for (i = be[pl]; i <= en[pl] && i + m - 1 <= n; i++) {
    if (i >= l && i <= r) ans = min(ans, sum);
    if (a[i] < y) sum--;
    if (a[i + m] < y) sum++;
  }
  if (pl == pr) return;
  sum = Fr[pr] + D[pr];
  for (i = be[pr]; i <= en[pr] && i + m - 1 <= n; i++) {
    if (i >= l && i <= r) ans = min(ans, sum);
    if (a[i] < y) sum--;
    if (a[i + m] < y) sum++;
  }
  for (i = pl + 1; i < pr; i++) ans = min(ans, D[i] + Mn[i]);
}
int main() {
  int i, j, k, l, r, pl, pr;
  scanf("%d %d", &n, &m);
  for (i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = i;
  scanf("%d", &q);
  sort(b + 1, b + n + 1, cmp);
  for (i = 1; i <= n; i++) en[i / 455] = i;
  for (i = n; i >= 1; i--) be[i / 455] = i;
  for (i = 0; i <= n / 455; i++) {
    if (i) {
      for (j = 0; j <= n / 455; j++) {
        d[i][j] = d[i - 1][j];
        mn[i][j] = mn[i - 1][j];
        fr[i][j] = fr[i - 1][j];
      }
    }
    for (j = be[i]; j <= en[i]; j++) {
      l = max(1, b[j] - m + 1), r = b[j];
      pl = l / 455, pr = r / 455;
      if (pl == pr) {
        for (k = l; k <= r; k++) val[k]++;
        mn[i][pl] = (1 << 30);
        for (k = be[pl]; k <= en[pl]; k++) mn[i][pl] = min(mn[i][pl], val[k]);
        fr[i][pl] = val[be[pl]];
      } else {
        for (k = l; k <= en[pl]; k++) val[k]++;
        mn[i][pl] = (1 << 30);
        for (k = be[pl]; k <= en[pl]; k++) mn[i][pl] = min(mn[i][pl], val[k]);
        fr[i][pl] = val[be[pl]];
        for (k = be[pr]; k <= r; k++) val[k]++;
        for (k = pl + 1; k < pr; k++) d[i][k]++;
        mn[i][pr] = (1 << 30);
        for (k = be[pr]; k <= en[pr]; k++) mn[i][pr] = min(mn[i][pr], val[k]);
        fr[i][pr] = val[be[pr]];
      }
      md[j][0] = mn[i][pl];
      md[j][1] = mn[i][pr];
    }
  }
  while (q--) {
    scanf("%d %d %d", &l, &r, &k);
    k ^= ans;
    solve(l, r, k);
    printf("%d\n", ans);
  }
  return 0;
}