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 N = 2e5 + 25;
const int B = 800;
const int M = 255;
const int B2 = 1666;
int n, k, a[N], l[N], r[N], e[N], b[N], d[N];
int m, bl[M], br[M], s[M], t[M][B2], f[M][B2], g[M][B2];
int q, w, h[N], u[N];
vector<int> v[N];
void go(int x, int y, int z) {
  if (l[x] < 0) {
    l[x] = y;
    e[x] = z;
  } else
    r[x] = y - 1;
  u[b[x]] = 1;
}
int main() {
  int i, j, x, y, z, o, p;
  scanf("%d%d", &n, &k);
  for (i = 1; i <= n; i = i + 1) {
    scanf("%d", a + i);
    if (i % B == 1) m++, bl[m] = i;
    b[i] = m, br[m] = i;
    h[i] = a[i];
  }
  sort(h + 1, h + n + 1);
  w = unique(h + 1, h + n + 1) - h - 1;
  for (i = 1; i <= n; i = i + 1) {
    a[i] = lower_bound(h + 1, h + w + 1, a[i]) - h;
    v[a[i]].push_back(i);
    l[i] = -1, r[i] = w;
  }
  for (x = 1; x <= w; x = x + 1) {
    d[x] = d[x - 1];
    for (y = v[x].size(); y--;) {
      i = v[x][y];
      if (i >= k)
        go(i - k + 1, x, 1);
      else
        d[x]++;
      if (i < n) go(i + 1, x, -1);
    }
    for (i = 1; i <= m; i = i + 1) {
      if (u[i]) {
        t[i][++s[i]] = x;
        o = 0, p = 0;
        for (j = bl[i]; j <= br[i]; j = j + 1)
          if (l[j] <= x && x <= r[j]) o += e[j], p = min(p, o);
        f[i][s[i]] = o, g[i][s[i]] = p;
        u[i] = 0;
      }
    }
  }
  p = 0;
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d%d", &x, &y, &z);
    z ^= p;
    z = lower_bound(h + 1, h + w + 1, z) - h - 1;
    o = d[z];
    for (i = 1; i < b[x]; i = i + 1) {
      j = upper_bound(t[i] + 1, t[i] + s[i] + 1, z) - t[i] - 1;
      o += f[i][j];
    }
    i = b[x];
    for (j = bl[i]; j <= x; j = j + 1)
      if (l[j] <= z && z <= r[j]) o += e[j];
    p = o;
    if (b[x] != b[y]) {
      for (j = x + 1; j <= br[i]; j = j + 1)
        if (l[j] <= z && z <= r[j]) o += e[j], p = min(p, o);
      for (i = b[x] + 1; i < b[y]; i = i + 1) {
        j = upper_bound(t[i] + 1, t[i] + s[i] + 1, z) - t[i] - 1;
        p = min(p, o + g[i][j]);
        o += f[i][j];
      }
      i = b[y];
      for (j = bl[i]; j <= y; j = j + 1)
        if (l[j] <= z && z <= r[j]) o += e[j], p = min(p, o);
    } else {
      for (j = x + 1; j <= y; j = j + 1)
        if (l[j] <= z && z <= r[j]) o += e[j], p = min(p, o);
    }
    printf("%d\n", p);
  }
  return 0;
}