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;
struct data {
  int w, p;
} t[200009];
struct Blo {
  int a[502], fr[502], tag[502];
} B[502];
int a[200009], bl[200009], L[200009], R[200009], w[200009], fr[200009],
    tag[200009], zx[200009], f[200009][2], blo, ans = 0, n, m, qes;
inline bool cmp(const data &A, const data &B) { return A.w < B.w; }
inline int Find(int x) {
  int l = 1, r = n, p = 0;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (t[mid].w <= x)
      l = mid + 1, p = mid;
    else
      r = mid - 1;
  }
  return p;
}
inline void work(int l, int r, int x) {
  ans = 1e9;
  int p = Find(x - 1);
  if (!p) {
    puts("0"), ans = 0;
    return;
  }
  for (int i = 1; i <= bl[n]; i++)
    tag[i] = 0, zx[i] = B[bl[p] - 1].a[i], fr[i] = B[bl[p] - 1].fr[i];
  for (int i = L[bl[p]]; i <= p; i++) {
    int hl = max(1, t[i].p + 1 - m), hr = t[i].p;
    if (bl[hl] != bl[hr]) tag[bl[hl] + 1]++, tag[bl[hr]]--;
    zx[bl[hl]] = f[i][0], zx[bl[hr]] = f[i][1];
    if (hl == L[bl[hl]]) ++fr[bl[hl]];
    if (bl[hl] != bl[hr]) ++fr[bl[hr]];
  }
  for (int i = 1; i <= bl[n]; i++) tag[i] += tag[i - 1];
  for (int i = 1; i <= bl[n]; i++) tag[i] += B[bl[p] - 1].tag[i];
  int sum = fr[bl[l]] + tag[bl[l]];
  for (int i = L[bl[l]]; i <= R[bl[l]]; i++) {
    if (i >= l && i <= r) ans = min(ans, sum);
    if (a[i] < x) --sum;
    if (a[i + m] < x) ++sum;
  }
  for (int i = bl[l] + 1; i < bl[r]; i++) ans = min(ans, tag[i] + zx[i]);
  sum = fr[bl[r]] + tag[bl[r]];
  for (int i = L[bl[r]]; i <= R[bl[r]]; i++) {
    if (i >= l && i <= r) ans = min(ans, sum);
    if (a[i] < x) --sum;
    if (a[i + m] < x) ++sum;
  }
  printf("%d\n", ans);
}
inline void rebuild(int x) {
  zx[x] = 1e9, fr[x] = w[L[x]];
  for (int i = L[x]; i <= R[x]; i++) zx[x] = min(zx[x], w[i]);
}
int main() {
  scanf("%d%d", &n, &m);
  blo = sqrt(n);
  for (int i = 1; i <= n; i++) scanf("%d", a + i), t[i].p = i, t[i].w = a[i];
  sort(t + 1, t + n + 1, cmp);
  for (int i = 1; i <= n; i++) bl[i] = (i - 1) / blo + 1;
  for (int i = 1; i <= bl[n]; i++)
    L[i] = (i - 1) * blo + 1, R[i] = min(i * blo, n);
  for (int i = 1; i <= bl[n]; i++) {
    for (int j = L[i]; j <= R[i]; j++) {
      int p = t[j].p, l = max(1, p + 1 - m), r = p;
      for (int k = l; k <= min(r, R[bl[l]]); k++) ++w[k];
      if (bl[l] != bl[r])
        for (int k = L[bl[r]]; k <= r; k++) ++w[k];
      for (int k = bl[l] + 1; k < bl[r]; k++) tag[k]++;
      rebuild(bl[l]), rebuild(bl[r]);
      f[j][0] = zx[bl[l]], f[j][1] = zx[bl[r]];
    }
    for (int j = 1; j <= bl[n]; j++)
      B[i].a[j] = zx[j], B[i].fr[j] = fr[j], B[i].tag[j] = tag[j];
  }
  scanf("%d", &qes);
  for (int i = 1, l, r, x; i <= qes; i++)
    scanf("%d%d%d", &l, &r, &x), work(l, r, x ^ ans);
  return 0;
}