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 maxn = 200000 + 5;
const int mult = 9;
const int blsize = (1 << mult);
const int INF = (1 << 30);
pair<int, int> music[maxn];
int Maxval[blsize][blsize], front[blsize][blsize], update[blsize][2 * blsize];
int arr[maxn], curval[maxn];
int curMax[blsize], curtag[blsize];
int n, m;
inline bool is_first(int idx) { return (idx & (blsize - 1)) == 0; }
inline int bl_idx(int idx) { return (idx >> mult) + (idx >= n ? 1 : 0); }
inline int first_idx(int blid) { return blid << mult; }
inline int last_idx(int blid) {
  return min(n - 1, first_idx(blid) + blsize - 1);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d", arr + i);
    music[i].first = -arr[i];
    music[i].second = i;
  }
  sort(music, music + n);
  int totbl = (n + blsize - 1) / blsize;
  for (int i = 0; i < n; i++) {
    if (is_first(i)) {
      int curtime = bl_idx(i);
      for (int j = 0; j < n; j++) curval[j] += curtag[bl_idx(j)];
      for (int j = 0; j < totbl; j++) {
        curMax[j] += curtag[j];
        Maxval[curtime][j] = curMax[j];
        front[curtime][j] = curval[first_idx(j)];
        curtag[j] = 0;
      }
    }
    int R = music[i].second, L = max(0, R - m + 1), sizeb = 0,
        tochange[] = {totbl, totbl};
    for (int j = L; j <= R; j++) {
      int curbl = bl_idx(j);
      if (is_first(j) && R >= last_idx(curbl))
        curtag[curbl]++, j = last_idx(curbl);
      else {
        curval[j]++;
        curMax[curbl] = max(curMax[curbl], curval[j]);
        if (sizeb == 0 || tochange[sizeb - 1] != curbl)
          tochange[sizeb++] = curbl;
      }
    }
    int curtime = bl_idx(i), idx = i - first_idx(curtime);
    for (int j = 0; j < 2; j++)
      update[curtime][2 * idx + j] =
          (curMax[tochange[j]] << mult) + tochange[j];
  }
  int query, ans = 0;
  scanf("%d", &query);
  while (query--) {
    int qL, qR, qv;
    scanf("%d%d%d", &qL, &qR, &qv);
    qL--, qR--, qv ^= ans;
    int idx = upper_bound(music, music + n, make_pair(-qv, INF)) - music - 1;
    if (idx < 0) {
      printf("%d\n", ans = m);
      continue;
    }
    int curtime = bl_idx(idx);
    for (int i = 0; i < totbl; i++)
      curMax[i] = Maxval[curtime][i], curtag[i] = 0;
    int st = first_idx(curtime);
    for (int i = st; i <= idx; i++) {
      int R = music[i].second, L = max(0, R - m + 1);
      if (L != first_idx(bl_idx(L))) L = last_idx(bl_idx(L)) + 1;
      if (R == last_idx(bl_idx(R))) R++;
      if (bl_idx(L) <= bl_idx(R)) curtag[bl_idx(L)]++, curtag[bl_idx(R)]--;
      for (int j = 0; j < 2; j++) {
        int xx = update[curtime][2 * (i - st) + j];
        curMax[xx & (blsize - 1)] = xx >> mult;
      }
    }
    for (int i = 1; i < totbl; i++) curtag[i] += curtag[i - 1];
    ans = 0;
    int val = -1;
    for (int i = qL; i <= qR; i++) {
      int curbl = bl_idx(i);
      if (is_first(i) && qR >= last_idx(curbl))
        ans = max(ans, curMax[curbl] + curtag[curbl]), i = last_idx(curbl),
        val = -1;
      else {
        if (val == -1) {
          val = front[curtime][curbl];
          int ftp = first_idx(curbl);
          for (int j = st; j <= idx; j++)
            if (ftp <= music[j].second &&
                ftp >= max(0, music[j].second - m + 1))
              val++;
          while (ftp != i) {
            val -= (arr[ftp] >= qv), val += (arr[ftp + m] >= qv);
            ftp++;
          }
        }
        ans = max(ans, val);
        val -= (arr[i] >= qv);
        val += (arr[i + m] >= qv);
      }
    }
    printf("%d\n", ans = m - ans);
  }
}