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;
template <class T>
void setmax(T &a, T b) {
  if (b > a) a = b;
}
template <class T>
void setmin(T &a, T b) {
  if (b < a) a = b;
}
template <class T>
T gcd(T a, T b) {
  return b == 0 ? a : gcd(b, a % b);
}
const int MAXN = 200010;
const int MAXNum = 655;
const int MAXSize = 455;
pair<int, int> a[MAXN];
int n, m;
int bv[MAXNum][MAXNum], bv0[MAXNum][MAXNum], bvl[MAXN], bvr[MAXN];
vector<int> bevents[MAXNum];
int bsize, bnum;
int bfirst(int p) { return (p - 1) * bsize + 1; }
int blast(int p) { return min(n, p * bsize); }
int bid(int i) { return (i - 1) / bsize + 1; }
void preprocess() {
  sort(a + 1, a + n + 1, greater<pair<int, int> >());
  static int nums[MAXN], val[MAXNum], buf[MAXNum];
  bsize = 450;
  bnum = (n - 1) / bsize + 1;
  memset(nums, 0, sizeof(nums));
  memset(val, 0, sizeof(val));
  memset(buf, 0, sizeof(buf));
  memset(bv[0], 0, sizeof(bv[0]));
  memset(bv0[0], 0, sizeof(bv0[0]));
  for (int i = int(1); i <= int(bnum); ++i) bevents[i].clear();
  for (int k = int(1); k <= int(n); ++k) {
    int l = max(1, a[k].second - m + 1), r = a[k].second;
    int vl0 = val[bid(l)], vr0 = val[bid(r)];
    for (int i = l; i <= r;) {
      int p = bid(i);
      if (i == bfirst(p) && blast(p) <= r) {
        val[p]++;
        buf[p]++;
        i = blast(p) + 1;
      } else {
        if (buf[p] != 0) {
          int x = bfirst(p), y = blast(p);
          for (int j = int(x); j <= int(y); ++j) nums[j] += buf[p];
          buf[p] = 0;
        }
        for (int j = min(r, blast(p)); i <= j; ++i) {
          nums[i]++;
          setmax(val[p], nums[i]);
        }
      }
    }
    bvl[k] = val[bid(l)] - vl0;
    bvr[k] = val[bid(r)] - vr0;
    if (bid(l) == bid(r)) bvr[k] = 0;
    if (k % bsize == 0) {
      for (int p = int(1); p <= int(bnum); ++p) {
        bv[k / bsize][p] = val[p];
        bv0[k / bsize][p] = buf[p] + nums[bfirst(p)];
      }
    }
    bool z = false;
    if (l != bfirst(bid(l))) bevents[bid(l)].push_back(k), z = true;
    if (bid(l) != bid(r) || !z) bevents[bid(r)].push_back(k);
  }
}
int cnt;
int query_block(int k0, int l, int r) {
  assert(bid(l) == bid(r));
  int p = bid(l), first = bfirst(p), k1 = k0 / bsize * bsize;
  int v[MAXSize];
  memset(v, 0, sizeof(v));
  for (int k : bevents[p]) {
    ++cnt;
    if (k > k1) break;
    int x = max(0, a[k].second - m + 1 - first);
    int y = min(bsize - 1, a[k].second - first);
    if (x <= y) v[x]++, v[y + 1]--;
  }
  int delta = bv0[k0 / bsize][p] - v[0];
  for (int k = int(k1 + 1); k <= int(k0); ++k) {
    int x = max(0, a[k].second - m + 1 - first);
    int y = min(bsize - 1, a[k].second - first);
    if (x <= y) v[x]++, v[y + 1]--;
  }
  for (int i = int(0); i <= int(bsize - 1); ++i) {
    v[i + 1] += v[i];
    v[i] += delta;
  }
  l = max(l - first, 0);
  r = min(r - first, bsize - 1);
  int ans = 0;
  for (int i = int(l); i <= int(r); ++i) setmax(ans, v[i]);
  return ans;
}
int query_history(int k, int l, int r) {
  static int val[MAXNum], buf[MAXNum];
  memmove(val, bv[k / bsize], sizeof(val));
  memset(buf, 0, sizeof(buf));
  for (int cur = int(k / bsize * bsize + 1); cur <= int(k); ++cur) {
    int x = max(1, a[cur].second - m + 1), y = a[cur].second;
    x = bid(x), y = bid(y);
    if (bvl[cur] != 0) {
      buf[x] += bvl[cur];
      buf[x + 1] -= bvl[cur];
    }
    if (bvr[cur] != 0) {
      buf[y] += bvr[cur];
      buf[y + 1] -= bvr[cur];
    }
    ++x, --y;
    if (x <= y) buf[x] += 1, buf[y + 1] -= 1;
  }
  for (int i = int(0); i <= int(bnum); ++i) {
    buf[i + 1] += buf[i];
    val[i] += buf[i];
  }
  int ans = 0;
  int cid = 1, cfirst = 1, clast = bsize;
  while (clast < l) ++cid, cfirst += bsize, clast += bsize;
  for (int i = l; i <= r;) {
    if (i == cfirst && clast <= r) {
      setmax(ans, val[cid]);
      i = clast + 1;
    } else {
      int j = min(clast, r);
      setmax(ans, query_block(k, i, j));
      i = j + 1;
    }
    ++cid, cfirst += bsize, clast += bsize;
  }
  return ans;
}
int query(int l, int r, int q) {
  int i = int(lower_bound(a + 1, a + n + 1, make_pair(q, 0),
                          greater<pair<int, int> >()) -
              a);
  assert(i >= 1 && i <= n + 1);
  int ans = m - query_history(i - 1, l, r);
  return ans;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = int(1); i <= int(n); ++i)
    scanf("%d", &a[i].first), a[i].second = i;
  preprocess();
  int cs;
  scanf("%d", &cs);
  int pans = 0;
  while (cs--) {
    int l, r, x;
    scanf("%d%d%d", &l, &r, &x);
    int q = x ^ pans;
    int ans = query(l, r, q);
    printf("%d\n", ans);
    pans = ans;
  }
  return 0;
}