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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const bool DEBUG = false;
const int MAXN = DEBUG ? 400 : 200000;
const int BLOCKSZ = DEBUG ? 20 : 500;
const int MAXBLOCKS = (MAXN + BLOCKSZ - 1) / BLOCKSZ;
const int MAXBSTATES = 2 * BLOCKSZ + 1;
const int STEPSZ = DEBUG ? 20 : 500;
const int MAXSTEPS = MAXN / STEPSZ + 1;
const int MAXSEG = 1 << 19;
bool writedebug = false;
int sval[MAXSEG], smin[MAXSEG], scnt;
void seginit(int x, int l, int r) {
  sval[x] = smin[x] = 0;
  if (l == r) return;
  int m = l + (r - l) / 2;
  seginit(2 * x + 1, l, m);
  seginit(2 * x + 2, m + 1, r);
}
void seginit(int _scnt) {
  scnt = _scnt;
  seginit(0, 0, scnt - 1);
}
void segadd(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R) {
    ++sval[x];
    ++smin[x];
    return;
  }
  int m = l + (r - l) / 2;
  if (L <= m) segadd(2 * x + 1, l, m, L, R);
  if (m + 1 <= R) segadd(2 * x + 2, m + 1, r, L, R);
  smin[x] = sval[x] + min(smin[2 * x + 1], smin[2 * x + 2]);
}
void segadd(int L, int R) { segadd(0, 0, scnt - 1, L, R); }
int segmn(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R) return smin[x];
  int m = l + (r - l) / 2;
  if (R <= m) return sval[x] + segmn(2 * x + 1, l, m, L, R);
  if (L >= m + 1) return sval[x] + segmn(2 * x + 2, m + 1, r, L, R);
  return sval[x] +
         min(segmn(2 * x + 1, l, m, L, R), segmn(2 * x + 2, m + 1, r, L, R));
}
int segmn(int L, int R) { return segmn(0, 0, scnt - 1, L, R); }
int n, nlisten;
typedef struct X {
  int val, idx;
} X;
bool operator<(const X &a, const X &b) { return a.val < b.val; }
X x[MAXN];
int av[MAXN + 1], al[MAXN], ar[MAXN], na;
int bcv[MAXBLOCKS][MAXBSTATES], bcl[MAXBLOCKS][MAXBSTATES - 1],
    bcr[MAXBLOCKS][MAXBSTATES - 1], bcmn[MAXBLOCKS][MAXBSTATES], nbc[MAXBLOCKS];
int bd[MAXBLOCKS][MAXSTEPS];
int findai(int x) {
  int l = 0, r = na;
  while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (av[m] < x)
      l = m;
    else
      r = m;
  }
  return l;
}
int findbi(int i, int x) {
  int l = 0, r = nbc[i];
  while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (bcv[i][m] < x)
      l = m;
    else
      r = m;
  }
  return l;
}
void init() {
  sort(x, x + n);
  int nblocks = (n + BLOCKSZ - 1) / BLOCKSZ;
  seginit(nblocks * BLOCKSZ);
  na = 0, av[na++] = -1;
  for (int i = (0); i < (MAXBLOCKS); ++i)
    nbc[i] = 0, bcmn[i][nbc[i]] = 0, bcv[i][nbc[i]++] = -1;
  for (int i = (0); i < (n); ++i) {
    int l = max(0, x[i].idx - nlisten + 1), r = x[i].idx;
    int bl = l / BLOCKSZ, br = r / BLOCKSZ;
    al[na - 1] = bl, ar[na - 1] = br, av[na++] = x[i].val;
    if (l > bl * BLOCKSZ || r < bl * BLOCKSZ + BLOCKSZ - 1) {
      int cl = l - bl * BLOCKSZ, cr = bl == br ? r - br * BLOCKSZ : BLOCKSZ - 1;
      segadd(bl * BLOCKSZ + cl, bl * BLOCKSZ + cr);
      bcl[bl][nbc[bl] - 1] = cl, bcr[bl][nbc[bl] - 1] = cr,
                        bcmn[bl][nbc[bl]] =
                            segmn(bl * BLOCKSZ, bl * BLOCKSZ + BLOCKSZ - 1),
                        bcv[bl][nbc[bl]++] = x[i].val;
    }
    if (bl != br && r < br * BLOCKSZ + BLOCKSZ - 1) {
      int cl = 0, cr = r - br * BLOCKSZ;
      segadd(br * BLOCKSZ + cl, br * BLOCKSZ + cr);
      bcl[br][nbc[br] - 1] = cl, bcr[br][nbc[br] - 1] = cr,
                        bcmn[br][nbc[br]] =
                            segmn(br * BLOCKSZ, br * BLOCKSZ + BLOCKSZ - 1),
                        bcv[br][nbc[br]++] = x[i].val;
    }
  }
  seginit(nblocks);
  for (int j = (0); j < (nblocks); ++j) bd[j][0] = 0;
  for (int i = (0); i < (n); ++i) {
    int l = max(0, x[i].idx - nlisten + 1), r = x[i].idx;
    int cl = l / BLOCKSZ, cr = r / BLOCKSZ;
    if (l > cl * BLOCKSZ) ++cl;
    if (r < cr * BLOCKSZ + BLOCKSZ - 1) --cr;
    if (cl <= cr) segadd(cl, cr);
    if ((i + 1) % STEPSZ == 0)
      for (int j = (0); j < (nblocks); ++j)
        bd[j][(i + 1) / STEPSZ] = segmn(j, j);
  }
}
int curglob[MAXBLOCKS + 1];
int curloc[BLOCKSZ + 1];
int calc(int l, int r, int q) {
  int bl = l / BLOCKSZ, br = r / BLOCKSZ;
  for (int i = (bl); i <= (br); ++i) curglob[i] = 0;
  int ai = findai(q), astep = ai / STEPSZ;
  for (int i = (astep * STEPSZ); i < (ai); ++i) {
    int l = max(0, x[i].idx - nlisten + 1), r = x[i].idx;
    int cl = l / BLOCKSZ, cr = r / BLOCKSZ;
    if (l > cl * BLOCKSZ) ++cl;
    if (r < cr * BLOCKSZ + BLOCKSZ - 1) --cr;
    if (cl < bl) cl = bl;
    if (cl <= cr) curglob[cl]++, curglob[cr + 1]--;
  }
  for (int i = (bl + 1); i <= (br); ++i) curglob[i] += curglob[i - 1];
  for (int i = (bl); i <= (br); ++i) curglob[i] += bd[i][astep];
  int ret = INT_MAX;
  for (int i = (bl + 1); i <= (br - 1); ++i) {
    int bi = findbi(i, q);
    int cur = curglob[i] + bcmn[i][bi];
    if (cur < ret) ret = cur;
  }
  {
    int bi = findbi(bl, q), cl = l - bl * BLOCKSZ,
        cr = bl == br ? r - br * BLOCKSZ : BLOCKSZ - 1;
    for (int i = (cl); i <= (cr); ++i) curloc[i] = 0;
    for (int i = (0); i < (bi); ++i) {
      int dl = max(bcl[bl][i], cl), dr = bcr[bl][i];
      if (dl <= dr) ++curloc[dl], --curloc[dr + 1];
    }
    for (int i = (cl + 1); i <= (cr); ++i) curloc[i] += curloc[i - 1];
    int mnloc = curloc[cl];
    for (int i = (cl + 1); i <= (cr); ++i)
      if (curloc[i] < mnloc) mnloc = curloc[i];
    int cur = curglob[bl] + mnloc;
    if (cur < ret) ret = cur;
  }
  if (bl != br) {
    int bi = findbi(br, q), cl = 0, cr = r - br * BLOCKSZ;
    for (int i = (cl); i <= (cr); ++i) curloc[i] = 0;
    for (int i = (0); i < (bi); ++i) {
      int dl = max(bcl[br][i], cl), dr = bcr[br][i];
      if (dl <= dr) ++curloc[dl], --curloc[dr + 1];
    }
    for (int i = (cl + 1); i <= (cr); ++i) curloc[i] += curloc[i - 1];
    int mnloc = curloc[cl];
    for (int i = (cl + 1); i <= (cr); ++i)
      if (curloc[i] < mnloc) mnloc = curloc[i];
    int cur = curglob[br] + mnloc;
    if (cur < ret) ret = cur;
  }
  return ret;
}
void run() {
  scanf("%d%d", &n, &nlisten);
  for (int i = (0); i < (n); ++i) scanf("%d", &x[i].val);
  for (int i = (0); i < (n); ++i) x[i].idx = i;
  init();
  int nq;
  scanf("%d", &nq);
  int pret = 0;
  for (int qi = (0); qi < (nq); ++qi) {
    int l, r, x;
    scanf("%d%d%d", &l, &r, &x);
    --l, --r;
    int q = x ^ pret;
    int ret = calc(l, r, q);
    printf("%d\n", ret);
    pret = ret;
  }
}
int calcbf(int l, int r, int q) {
  int ret = INT_MAX;
  for (int i = (l); i <= (r); ++i) {
    int cur = 0;
    for (int j = (0); j < (n); ++j)
      if (x[j].val < q && x[j].idx >= i && x[j].idx <= i + nlisten - 1) ++cur;
    if (cur < ret) ret = cur;
  }
  return ret;
}
int myrand() { return rand() * (1 << 15) + rand(); }
void test() {
  bool err = false;
  for (int testnr = 0; !err; ++testnr) {
    writedebug = testnr == 0;
    n = MAXN, nlisten = rand() % n + 1;
    for (int i = (0); i < (n); ++i) x[i].idx = i, x[i].val = myrand() % 10;
    init();
    for (int i = (0); i < (n); ++i) {
      int l = myrand() % (n - nlisten + 1), r = myrand() % (n - nlisten + 1),
          q = myrand() % 10;
      if (l > r) swap(l, r);
      int have = calc(l, r, q), want = calcbf(l, r, q);
      if (have != want) {
        if (!err) {
          puts("");
          for (int j = (0); j < (n); ++j)
            printf("x[%d]=%d\n", x[j].idx, x[j].val);
          err = true;
        }
        printf("%d %d %d -> have=%d vs want=%d\n", l, r, q, have, want);
      }
    }
    printf(".");
  }
}
int main() {
  if (DEBUG)
    test();
  else
    run();
  return 0;
}