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 = 200010, M = 450;
int pos[N], L[M], R[M], v[N], lz[M], f[M], s[N], pre[M][M], fr[M][M], a[N],
    g[N][2], id[N], c[M];
inline int gi() {
  int x = 0, o = 1;
  char ch = getchar();
  while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
  if (ch == '-') o = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * o;
}
inline bool cmp(const int &x, const int &y) { return a[x] > a[y]; }
inline void update(int l, int r, int t) {
  int A = pos[l], B = pos[r];
  if (A == B) {
    for (int i = l; i <= r; i++) ++s[i];
    for (int i = L[A]; i <= R[A]; i++) g[t][0] = max(g[t][0], s[i]);
    return;
  }
  for (int i = l; i <= R[A]; i++) ++s[i];
  for (int i = L[A]; i <= R[A]; i++) g[t][0] = max(g[t][0], s[i]);
  for (int i = A + 1; i < B; i++) ++lz[i];
  for (int i = L[B]; i <= r; i++) ++s[i];
  for (int i = L[B]; i <= R[B]; i++) g[t][1] = max(g[t][1], s[i]);
}
inline void rebuild(int k, int n) {
  for (int i = 1; i <= n; i++) {
    for (int j = L[i]; j <= R[i]; j++)
      pre[k][i] = max(pre[k][i], s[j] += lz[i]);
    fr[k][i] = s[L[i]], lz[i] = 0;
  }
}
inline int query(int l, int r, int k, int A, int m) {
  int res = f[A], ret = 0;
  for (int i = L[A]; i < l; i++) res += (a[i + m] >= k) - (a[i] >= k);
  for (int i = l; i <= r; i++) {
    ret = max(ret, res);
    res += (a[i + m] >= k) - (a[i] >= k);
  }
  return ret;
}
int main() {
  int n, m, q, k, sz, ans = 0, cnt;
  cin >> n >> m, sz = sqrt(n) + 1e-9;
  for (int i = 1; i <= n; i++) a[i] = v[i] = gi(), id[i] = i;
  sort(v + 1, v + 1 + n);
  k = unique(v + 1, v + 1 + n) - v - 1;
  for (int i = 1; i <= n; i++) a[i] = lower_bound(v + 1, v + 1 + k, a[i]) - v;
  sort(id + 1, id + 1 + n, cmp);
  for (int i = 1; i <= n; i++) {
    int t = (i - 1) / sz + 1;
    pos[i] = t, R[t] = i, L[t] = L[t] ? L[t] : i;
  }
  cnt = pos[n];
  for (int i = 1; i <= n; i++) {
    if (pos[i] != pos[i - 1]) {
      rebuild(pos[i - 1], cnt);
      c[pos[i] - 1] = a[id[i]];
    }
    update(max(1, id[i] - m + 1), id[i], i);
  }
  cin >> q;
  while (q--) {
    int l = gi(), r = gi(), x = lower_bound(v + 1, v + 1 + k, gi() ^ ans) - v,
        p = 1, C = pos[l], D = pos[r];
    while (p < cnt && c[p] >= x) ++p;
    for (int i = 1; i <= cnt; i++)
      lz[i] = 0, s[i] = pre[p - 1][i], f[i] = fr[p - 1][i];
    for (int i = L[p]; i <= R[p] && a[id[i]] >= x; i++) {
      int l = max(1, id[i] - m + 1), r = id[i], A = pos[l], B = pos[r];
      if (A == B)
        s[A] = g[i][0];
      else
        ++lz[A + 1], --lz[B], s[A] = g[i][0], s[B] = g[i][1];
      if (L[C] >= l && L[C] <= r) ++f[C];
      if (C != D && L[D] >= l && L[D] <= r) ++f[D];
    }
    for (int i = 1; i <= cnt; i++) lz[i] += lz[i - 1];
    if (C == D)
      ans = query(l, r, x, C, m);
    else {
      ans = max(query(l, R[C], x, C, m), query(L[D], r, x, D, m));
      for (int i = C + 1; i < D; i++) ans = max(ans, s[i] + lz[i]);
    }
    printf("%d\n", ans = m - ans);
  }
  return 0;
}