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 M = 512;
const int N = M * M;
int blvalue[M][M];
int ftvalue[M][M];
int exvalue[M][2 * M];
int a[N];
pair<int, int> na[N];
int va[N];
int push[M];
int bl[M];
int n, m;
int blcount;
const int mult = 9;
const int blsz = (1 << mult);
inline bool is_first(int idx) { return (idx & (blsz - 1)) == 0; }
inline int bl_idx(int idx) {
  if (idx >= n) {
    return (idx >> mult) + 1;
  }
  return idx >> mult;
}
inline int first_idx(int blid) { return blid << mult; }
inline int last_idx(int blid) { return min(n - 1, first_idx(blid) + blsz - 1); }
const int INF = 1000 * 1000 * 1000;
int main() {
  scanf("%d %d", &n, &m);
  blcount = (n + blsz - 1) / blsz;
  for (int i = 0; i < int(n); i++) scanf("%d", &a[i]);
  for (int i = 0; i < int(n); i++) na[i] = make_pair(-a[i], i);
  sort(na, na + n);
  for (int iter = 0; iter < int(n); iter++) {
    if (is_first(iter)) {
      int curbl = bl_idx(iter);
      for (int i = 0; i < int(n); i++) va[i] = va[i] + push[bl_idx(i)];
      for (int i = 0; i < int(blcount); i++) {
        bl[i] += push[i];
        blvalue[curbl][i] = bl[i];
        ftvalue[curbl][i] = va[first_idx(i)];
        push[i] = 0;
      }
    }
    int r = na[iter].second;
    int l = max(0, r - m + 1);
    int blocks[] = {blcount, blcount};
    int szb = 0;
    for (int i = l; i <= r;) {
      int curbl = bl_idx(i);
      if (is_first(i) && last_idx(curbl) <= r) {
        push[curbl]++;
        i = last_idx(curbl) + 1;
      } else {
        va[i]++;
        bl[curbl] = max(bl[curbl], va[i]);
        if (szb == 0 || blocks[szb - 1] != curbl) {
          blocks[szb++] = curbl;
        }
        i++;
      }
    }
    szb = 2;
    int curbl = bl_idx(iter);
    int idx = iter - first_idx(curbl);
    for (int i = 0; i < int(szb); i++) {
      exvalue[curbl][2 * idx + i] = (bl[blocks[i]] << mult) + blocks[i];
    }
  }
  int query;
  scanf("%d", &query);
  int last_ans = 0;
  for (int it = 0; it < int(query); it++) {
    int l, r, q;
    scanf("%d %d %d", &l, &r, &q);
    l--, r--;
    q ^= last_ans;
    int idx = upper_bound(na, na + n, make_pair(-q, INF)) - na;
    idx--;
    if (idx < 0) {
      printf("%d\n", m);
      last_ans = m;
      continue;
    }
    int curbl = bl_idx(idx);
    for (int i = 0; i < int(blcount); i++) {
      bl[i] = blvalue[curbl][i];
      push[i] = 0;
    }
    int first = first_idx(curbl);
    for (int i = first; i <= idx; i++) {
      int nr = na[i].second;
      int nl = max(0, nr - m + 1);
      if (nl != first_idx(bl_idx(nl))) {
        nl = last_idx(bl_idx(nl)) + 1;
      }
      if (nr == last_idx(bl_idx(nr))) {
        nr++;
      }
      if (bl_idx(nl) <= bl_idx(nr)) {
        push[bl_idx(nl)]++;
        push[bl_idx(nr)]--;
      }
      for (int j = 0; j < int(2); j++) {
        int blid = exvalue[curbl][2 * (i - first) + j];
        int vt = blid >> mult;
        blid &= (blsz - 1);
        bl[blid] = vt;
      }
    }
    for (int i = 0; i < int(blcount); i++) {
      if (i > 0) push[i] += push[i - 1];
    }
    int maxAns = 0;
    int pv = -1;
    for (int i = l; i <= r;) {
      int blid = bl_idx(i);
      if (is_first(i) && last_idx(blid) <= r) {
        maxAns = max(maxAns, bl[blid] + push[blid]);
        i = last_idx(blid) + 1;
        pv = -1;
      } else {
        if (pv == -1) {
          pv = ftvalue[curbl][blid];
          int ftp = first_idx(blid);
          for (int j = first; j <= idx; j++) {
            if (ftp <= na[j].second && ftp >= max(na[j].second - m + 1, 0)) {
              pv++;
            }
          }
          while (ftp != i) {
            pv -= (a[ftp] >= q);
            pv += (a[ftp + m] >= q);
            ftp++;
          }
        }
        maxAns = max(maxAns, pv);
        pv -= (a[i] >= q);
        pv += (a[i + m] >= q);
        i++;
      }
    }
    maxAns = m - maxAns;
    printf("%d\n", maxAns);
    last_ans = maxAns;
  }
}