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 maxn(2e5 + 5);
int n, m, s, a[maxn], bl[maxn], br[maxn], b[maxn], o[maxn], len, id[maxn], blk;
int mn[505][505], st[505][505], tag[505], w[maxn], pmn[maxn], smn[maxn];
int curmn[505], curst[505], curtag[505];
inline void Modify(int l, int r, int id) {
  int i;
  pmn[id] = smn[id] = 1 << 30;
  if (b[l] == b[r])
    for (i = l; i <= r; ++i) ++w[i];
  else {
    for (i = l; i <= br[l]; ++i) ++w[i];
    for (i = bl[r]; i <= r; ++i) ++w[i];
    for (i = b[l] + 1; i < b[r]; ++i) ++tag[i];
  }
  for (i = bl[l]; i <= br[l]; ++i) pmn[id] = min(pmn[id], w[i]);
  for (i = bl[r]; i <= br[r]; ++i) smn[id] = min(smn[id], w[i]);
}
inline int Binary(int v) {
  int l = 1, r = n, mid, ret = -1;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (o[a[id[mid]]] <= v)
      ret = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  return ret;
}
inline int Query(int l, int r, int x) {
  int val = curst[b[l]], i, ret = 1 << 30;
  for (i = bl[l]; i < l; ++i) val += (a[i + m] <= x) - (a[i] <= x);
  for (i = l; i <= r; ++i)
    ret = min(ret, val), val += (a[i + m] <= x) - (a[i] <= x);
  return ret;
}
int main() {
  int i, j, ans = 0, l, r, x, ql, qr;
  scanf("%d%d", &n, &m), len = n;
  for (i = 1; i <= n; ++i) scanf("%d", &a[i]), o[i] = a[i], id[i] = i;
  sort(o + 1, o + len + 1), len = unique(o + 1, o + len + 1) - o - 1;
  for (i = 1; i <= n; ++i) a[i] = lower_bound(o + 1, o + len + 1, a[i]) - o;
  sort(id + 1, id + n + 1, [](int x, int y) { return a[x] < a[y]; });
  for (blk = sqrt(n), i = 1; i <= n; ++i)
    b[i] = (i - 1) / blk + 1, bl[i] = b[i] == b[i - 1] ? bl[i - 1] : i;
  for (i = n; i; --i) br[i] = b[i] == b[i + 1] ? br[i + 1] : i;
  memset(mn, 63, sizeof(mn)), memset(mn[0], 0, sizeof(mn[0]));
  for (i = 1; i <= n; ++i) {
    Modify(max(1, id[i] - m + 1), id[i], i);
    if (b[i] != b[i + 1]) {
      for (j = 1; j <= n; ++j) w[j] += tag[b[j]];
      for (j = 1; j <= b[n]; ++j) tag[j] = 0;
      for (j = 1; j <= n; ++j) {
        mn[b[i]][b[j]] = min(mn[b[i]][b[j]], w[j]);
        if (b[j] != b[j - 1]) st[b[i]][b[j]] = w[j];
      }
    }
  }
  scanf("%d", &s);
  while (s--) {
    scanf("%d%d%d", &l, &r, &x), x ^= ans, x = Binary(x - 1);
    if (x < 0) {
      printf("%d\n", ans = 0);
      continue;
    }
    for (i = 1; i <= b[n]; ++i)
      curmn[i] = mn[b[x] - 1][i], curst[i] = st[b[x] - 1][i], curtag[i] = 0;
    for (i = bl[x]; i <= x; ++i) {
      ql = max(1, id[i] - m + 1), qr = id[i];
      curmn[b[ql]] = pmn[i], curmn[b[qr]] = smn[i];
      if (b[ql] < b[qr]) ++curtag[b[ql] + 1], --curtag[b[qr]];
      if (ql <= bl[l] && bl[l] <= qr) ++curst[b[l]];
      if (ql <= bl[r] && bl[r] <= qr && (b[l] ^ b[r])) ++curst[b[r]];
    }
    for (i = 1; i <= b[n]; ++i)
      curtag[i] += curtag[i - 1], curmn[i] += curtag[i];
    if (b[l] == b[r])
      printf("%d\n", ans = Query(l, r, a[id[x]]));
    else {
      ans = min(Query(l, br[l], a[id[x]]), Query(bl[r], r, a[id[x]]));
      for (i = b[l] + 1; i < b[r]; ++i) ans = min(ans, curmn[i]);
      printf("%d\n", ans);
    }
  }
  return 0;
}