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;
int N, M, Q;
int a[200000];
int cid[200000];
int pInc[200000], pDec[200000];
bool cmp(int x, int y) { return a[x] < a[y]; }
vector<int> spoints[500];
vector<int> first[500];
vector<int> best[500];
int tmp[2000];
int dif[200001];
int slow(int l, int r, int x) {
  int ans = 1000000000;
  for (int i = l; i <= r; i++) {
    int cur = 0;
    for (int j = i; j < i + M; j++)
      if (a[j] < x) cur++;
    ans = min(ans, cur);
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(0);
  cin >> N >> M;
  for (int i = 0; i < N; i++) {
    cin >> a[i];
    cid[i] = i;
  }
  sort(cid, cid + N, cmp);
  for (int i = 0; i < N; i++) {
    spoints[i / 447].push_back(max(0, cid[i] - M + 1));
    spoints[i / 447].push_back(cid[i] + 1);
  }
  for (int i = 0; i * 447 < N; i++) {
    for (int j = 0; j < N; j += 447) spoints[i].push_back(j);
    spoints[i].push_back(N);
    sort(spoints[i].begin(), spoints[i].end());
    spoints[i].resize(distance(spoints[i].begin(),
                               unique(spoints[i].begin(), spoints[i].end())));
  }
  for (int i = 0; i < N; i++) {
    pInc[i] = lower_bound(spoints[i / 447].begin(), spoints[i / 447].end(),
                          max(0, cid[i] - M + 1)) -
              spoints[i / 447].begin();
    pDec[i] = lower_bound(spoints[i / 447].begin(), spoints[i / 447].end(),
                          cid[i] + 1) -
              spoints[i / 447].begin();
  }
  int lb = ((N - 1) / 447);
  for (int k = 0; k < spoints[lb].size(); k++) {
    best[lb].push_back(0), first[lb].push_back(0);
  }
  for (int i = N - 1; i > 0; i--) {
    dif[max(0, cid[i] - M + 1)]++, dif[cid[i] + 1]--;
    if (i % 447 == 0) {
      int b = (i / 447) - 1;
      int v = 0;
      int j = 0;
      int mx = 0;
      for (int k = 0; k <= N; k++) {
        v += dif[k];
        if (k == spoints[b][j]) {
          first[b].push_back(v);
          if (j) {
            best[b].push_back(mx);
          }
          mx = v;
          j++;
        } else
          mx = max(mx, v);
      }
    }
  }
  cin >> Q;
  int l, r, x;
  int ans;
  for (int i = 0; i < Q; i++) {
    cin >> l >> r >> x;
    if (i) x ^= ans;
    l--, r--;
    int b = 0;
    while ((b + 1) * 447 < N && a[cid[(b + 1) * 447]] < x) b++;
    for (int j = 0; j < spoints[b].size(); j++) tmp[j] = 0;
    for (int k = min(N, (b + 1) * 447) - 1; k >= 0 && a[cid[k]] >= x; k--)
      tmp[pInc[k]]++, tmp[pDec[k]]--;
    int lBlock = lower_bound(spoints[b].begin(), spoints[b].end(), l) -
                 spoints[b].begin();
    ans = 0;
    int v = first[b][lBlock];
    int ps = 0;
    for (int j = 0; j < lBlock; j++) ps += tmp[j];
    v += ps + tmp[lBlock];
    for (int j = spoints[b][lBlock] - 1; j >= l; j--) {
      if (a[j] >= x) v++;
      if (j + M < N && a[j + M] >= x) v--;
      if (j <= r) ans = max(ans, v);
    }
    int rBlock = upper_bound(spoints[b].begin(), spoints[b].end(), r) -
                 spoints[b].begin() - 1;
    v = first[b][rBlock] + ps;
    for (int j = lBlock; j <= rBlock; j++) v += tmp[j];
    for (int j = spoints[b][rBlock]; j <= r; j++) {
      if (j >= l) ans = max(ans, v);
      if (a[j] >= x) v--;
      if (j + M < N && a[j + M] >= x) v++;
    }
    for (int j = lBlock; j < rBlock; j++) {
      ps += tmp[j];
      ans = max(ans, ps + best[b][j]);
    }
    ans = M - ans;
    cout << ans << '\n';
  }
}