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;
namespace zyt {
template <typename T>
inline bool read(T &x) {
  char c;
  bool f = false;
  x = 0;
  do c = getchar();
  while (c != EOF && c != '-' && !isdigit(c));
  if (c == EOF) return false;
  if (c == '-') f = true, c = getchar();
  do x = x * 10 + c - '0', c = getchar();
  while (isdigit(c));
  if (f) x = -x;
  return true;
}
template <typename T>
inline void write(T x) {
  static char buf[20];
  char *pos = buf;
  if (x < 0) putchar('-'), x = -x;
  do *pos++ = x % 10 + '0';
  while (x /= 10);
  while (pos > buf) putchar(*--pos);
}
const int N = 2e5 + 10, B = 500, INF = 0x3f3f3f3f;
int n, m, arr[N], block, blnum, begin[B], belong[N];
int first[B][B], mn[B][B], buf[N];
pair<int, int> mdf[N], upd[N][2];
void get(const int x, int v, const int pos, int *const tmp) {
  for (int i = begin[pos]; i < begin[pos + 1]; i++) {
    tmp[i] = v;
    v -= (arr[i] <= x);
    if (i + m <= n) v += (arr[i + m] <= x);
  }
}
int work() {
  read(n), read(m);
  block = sqrt(n);
  blnum = ceil((double)n / block);
  for (int i = 1; i <= n; i++)
    read(arr[i]), mdf[i] = pair<int, int>(arr[i], i),
                  belong[i] = (i - 1) / block + 1;
  for (int i = 1; i <= blnum; i++) begin[i] = (i - 1) * block + 1;
  begin[blnum + 1] = n + 1;
  sort(mdf + 1, mdf + n + 1);
  for (int i = 1; i <= n; i++) arr[mdf[i].second] = i;
  for (int i = 1; i <= n; i++) {
    int pos = belong[i];
    if (i == begin[pos]) {
      memcpy(first[pos], first[pos - 1], sizeof(int[blnum + 1]));
      memcpy(mn[pos], mn[pos - 1], sizeof(int[blnum + 1]));
    }
    int r = mdf[i].second, l = max(1, r - m + 1);
    for (int j = belong[l] + 1; j < belong[r]; j++)
      ++mn[pos][j], ++first[pos][j];
    if (l == begin[belong[l]]) ++first[pos][belong[l]];
    get(i, first[pos][belong[l]], belong[l], buf);
    int tmp = mn[pos][belong[l]];
    mn[pos][belong[l]] = INF;
    for (int j = begin[belong[l]]; j < begin[belong[l] + 1]; j++)
      mn[pos][belong[l]] = min(mn[pos][belong[l]], buf[j]);
    upd[i][0] = pair<int, int>(belong[l], mn[pos][belong[l]] - tmp);
    if (belong[l] < belong[r]) {
      ++first[pos][belong[r]];
      get(i, first[pos][belong[r]], belong[r], buf);
      tmp = mn[pos][belong[r]];
      mn[pos][belong[r]] = INF;
      for (int j = begin[belong[r]]; j < begin[belong[r] + 1]; j++)
        mn[pos][belong[r]] = min(mn[pos][belong[r]], buf[j]);
      upd[i][1] = pair<int, int>(belong[r], mn[pos][belong[r]] - tmp);
    }
  }
  int q, lastans = 0;
  read(q);
  while (q--) {
    int l, r, x;
    read(l), read(r), read(x);
    x ^= lastans;
    int t = lower_bound(mdf + 1, mdf + n + 1, pair<int, int>(x, 0)) - mdf - 1;
    if (!t) {
      lastans = 0;
      puts("0");
      continue;
    }
    static int fst[B], mm[B], add[B];
    memcpy(fst, first[belong[t] - 1], sizeof(int[blnum + 1]));
    memcpy(mm, mn[belong[t] - 1], sizeof(int[blnum + 1]));
    memset(add, 0, sizeof(int[blnum + 1]));
    for (int i = begin[belong[t]]; i <= t; i++) {
      int r = mdf[i].second, l = max(1, r - m + 1);
      if (l == begin[belong[l]]) ++fst[belong[l]];
      if (belong[l] != belong[r])
        ++fst[belong[r]], ++add[belong[l] + 1], --add[belong[r]];
      for (int j = 0; j < 2; j++)
        if (upd[i][j].first) mm[upd[i][j].first] += upd[i][j].second;
    }
    for (int i = 1; i <= blnum; i++) add[i] += add[i - 1];
    int ans = INF;
    for (int i = belong[l] + 1; i < belong[r]; i++)
      ans = min(ans, mm[i] + add[i]);
    get(t, fst[belong[l]] + add[belong[l]], belong[l], buf);
    for (int i = l; i < min(r + 1, begin[belong[l] + 1]); i++)
      ans = min(ans, buf[i]);
    if (belong[l] < belong[r]) {
      get(t, fst[belong[r]] + add[belong[r]], belong[r], buf);
      for (int i = begin[belong[r]]; i <= r; i++) ans = min(ans, buf[i]);
    }
    write(lastans = ans), putchar('\n');
  }
  return 0;
}
}  // namespace zyt
int main() { return zyt::work(); }