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 MX = 200005, BITS = 9, S = 1 << BITS, MASK = S - 1,
          CNT = (MX + S - 1) / S;
struct Upd {
  int pos, val, t;
  Upd(int pos, int val, int t) : pos(pos), val(val), t(t) {}
  Upd() {}
};
int n, m, q;
int a[MX], ord[MX];
int val[MX], whole[CNT], mx[CNT][CNT], wh[CNT][CNT];
vector<Upd> upd[CNT];
vector<vector<int> > save[CNT];
int bFrom[MX], bTo[MX], bInd[2], bMx[2], nbMx[2], uFrom[MX], uTo[MX];
bool cmp(const int &lhs, const int &rhs) { return a[lhs] > a[rhs]; }
int calcMx(int block) {
  int ret = 0;
  int from = block << BITS;
  int to = min(n - m, (block << BITS) | MASK);
  for (int k = from; k <= to; ++k) ret = max(ret, val[k] + whole[k >> BITS]);
  return ret;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < (int)(n); ++i) scanf("%d", a + i);
  for (int i = 0; i < (int)(n); ++i) ord[i] = i;
  sort(ord, ord + n, cmp);
  for (int i = 0;; ++i) {
    if (!(i & MASK)) {
      int cur = i >> BITS;
      for (int j = 0; j < (int)(n); ++j) {
        mx[cur][j >> BITS] = max(mx[cur][j >> BITS], val[j] + whole[j >> BITS]);
      }
      for (int j = 0; j < (int)(CNT); ++j) wh[cur][j] = whole[j];
    }
    if (i == n) break;
    int from = uFrom[i] = max(0, ord[i] - m + 1);
    int to = uTo[i] = min(n - m, ord[i]);
    bInd[0] = from >> BITS, bInd[1] = to >> BITS;
    for (int j = 0; j < (int)(2); ++j) bMx[j] = calcMx(bInd[j]);
    for (int j = from; j <= to;) {
      if (!(j & MASK) && j + S - 1 <= to) {
        ++whole[j >> BITS];
        j += S;
      } else {
        ++val[j];
        ++j;
      }
    }
    for (int j = 0; j < (int)(2); ++j) nbMx[j] = calcMx(bInd[j]);
    bFrom[i] = from >> BITS;
    bTo[i] = to >> BITS;
    if (nbMx[0] == bMx[0]) ++bFrom[i];
    if (nbMx[1] == bMx[1]) --bTo[i];
    if ((from & MASK) || to - from < MASK)
      upd[from >> BITS].push_back(Upd(from & MASK, +1, i));
    if ((to & MASK) != MASK || to - from < MASK) {
      if ((from >> BITS) != (to >> BITS))
        upd[to >> BITS].push_back(Upd(0, +1, i));
      upd[to >> BITS].push_back(Upd((to & MASK) + 1, -1, i));
    }
  }
  for (int i = 0; i < (int)(CNT); ++i)
    if ((int)upd[i].size() >= S) {
      vector<int> tmp(S + 1, 0);
      for (int j = 0; j < (int)(upd[i].size()); ++j) {
        tmp[upd[i][j].pos] += upd[i][j].val;
        if ((j & MASK) == MASK) save[i].push_back(tmp);
      }
    }
  scanf("%d", &q);
  int ans = 0;
  for (int query = 0; query < (int)(q); ++query) {
    int from, to, qual;
    scanf("%d%d%d", &from, &to, &qual), --from, --to, qual ^= ans;
    int lo = -1, hi = n - 1, mid;
    while (lo < hi) {
      mid = (lo + hi + 1) >> 1;
      if (a[ord[mid]] < qual)
        hi = mid - 1;
      else
        lo = mid;
    }
    if (lo == -1) {
      printf("%d\n", m);
      ans = m;
      continue;
    }
    qual = lo;
    bInd[0] = from >> BITS, bInd[1] = to >> BITS;
    ans = 0;
    for (int i = 0; i < (int)(2); ++i) {
      if (i == 1 && bInd[0] == bInd[1]) break;
      int cur = bInd[i];
      lo = 0, hi = (int)upd[cur].size();
      while (lo < hi) {
        mid = (lo + hi) >> 1;
        if (upd[cur][mid].t > qual)
          hi = mid;
        else
          lo = mid + 1;
      }
      vector<int> tmp;
      if ((lo >> BITS) > 0)
        tmp = save[cur][(lo >> BITS) - 1];
      else
        tmp.assign(S + 1, 0);
      for (int j = lo & (~MASK); j < lo; ++j)
        tmp[upd[cur][j].pos] += upd[cur][j].val;
      int va = wh[qual >> BITS][cur];
      for (int i = qual & (~MASK); i <= qual; ++i)
        if (uFrom[i] <= (cur << BITS) && uTo[i] >= (cur << BITS) + MASK) ++va;
      for (int j = 0; j < (int)(S); ++j) {
        va += tmp[j];
        if (((cur << BITS) | j) >= from && ((cur << BITS) | j) <= to)
          ans = max(ans, va);
      }
    }
    int wfrom = from >> BITS;
    int wto = to >> BITS;
    if ((from & MASK) || to - from < S) ++wfrom;
    if ((to & MASK) != MASK || to - from < S) --wto;
    vector<int> tmp(CNT + 1, 0);
    int wqual = qual >> BITS;
    for (int i = 0; i < (int)(CNT); ++i) tmp[i] = mx[wqual][i];
    for (int i = CNT - 1; i >= 1; --i) tmp[i] -= tmp[i - 1];
    for (int i = wqual << BITS; i <= qual; ++i)
      if (bTo[i] >= bFrom[i]) {
        ++tmp[bFrom[i]];
        --tmp[bTo[i] + 1];
      }
    int cur = 0;
    for (int i = 0; i < (int)(CNT); ++i) {
      cur += tmp[i];
      if (i >= wfrom && i <= wto) ans = max(ans, cur);
    }
    ans = m - ans;
    printf("%d\n", ans);
  }
  return 0;
}