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;
int arr[((1 << 18))];
pair<int, int> a[((1 << 18))];
int kd[19][((1 << 18))];
void Init(int root, int bas, int son, int d = 0) {
  assert(d < 19 and son <= 200000);
  if (bas == son) {
    kd[d][bas] = arr[bas];
    return;
  }
  Init(root * 2, bas, (bas + son) / 2, d + 1);
  Init(root * 2 + 1, (bas + son) / 2 + 1, son, d + 1);
  merge(kd[d + 1] + bas, kd[d + 1] + (bas + son) / 2 + 1,
        kd[d + 1] + (bas + son) / 2 + 1, kd[d + 1] + son + 1, kd[d] + bas);
}
int Query(int root, int bas, int son, int x, int y, int val, int d = 0) {
  assert(d < 19 and son <= 200000);
  if (son < x or y < bas) return 0;
  if (x <= bas and son <= y)
    return lower_bound(kd[d] + bas, kd[d] + son + 1, val) - (kd[d] + bas);
  return Query(root * 2, bas, (bas + son) / 2, x, y, val, d + 1) +
         Query(root * 2 + 1, (bas + son) / 2 + 1, son, x, y, val, d + 1);
}
int minimal_solver(int l, int r, int v) {
  int res = Query(1, 0, n - 1, l, min(n - 1, l + m - 1), v);
  int mini = res;
  for (int i = l; i <= r - 1; i++) {
    res -= (arr[i] < v);
    res += (arr[i + m] < v);
    mini = min(mini, res);
  }
  return mini;
}
int MINI[2 * ((1 << 18))], art[2 * ((1 << 18))];
void init(int root, int bas, int son) {
  MINI[root] = art[root] = 0;
  if (bas == son) return;
  init(root * 2, bas, (bas + son) / 2);
  init(root * 2 + 1, (bas + son) / 2 + 1, son);
}
int update(int root, int bas, int son, int x, int y) {
  if (son < x or y < bas) return MINI[root];
  if (x <= bas and son <= y) {
    art[root]++;
    MINI[root]++;
    return MINI[root];
  }
  return MINI[root] =
             min(update(root * 2, bas, (bas + son) / 2, x, y),
                 update(root * 2 + 1, (bas + son) / 2 + 1, son, x, y)) +
             art[root];
}
int query(int root, int bas, int son, int x, int y) {
  if (son < x or y < bas) return 1000000007LL;
  if (x <= bas and son <= y) return MINI[root];
  return min(query(root * 2, bas, (bas + son) / 2, x, y),
             query(root * 2 + 1, (bas + son) / 2 + 1, son, x, y)) +
         art[root];
}
int s[((1 << 18)) / ((1 << 13))][((1 << 18))];
void generate() {
  init(1, 0, n - 1);
  for (int i = 0; i <= n - 1; i++) {
    for (int g = 0; g <= (n - 1) / ((1 << 13)); g++)
      s[g][i] = query(1, 0, n - 1, g * ((1 << 13)),
                      min(n - 1, (g + 1) * ((1 << 13)) - 1));
    update(1, 0, n - 1, max(0, a[i].second - m + 1), a[i].second);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 0; i <= n - 1; i++) {
    cin >> arr[i];
    a[i] = make_pair(arr[i], i);
  }
  sort(a, a + n);
  Init(1, 0, n - 1);
  generate();
  int q;
  cin >> q;
  int last = 0;
  int cnt = 0;
  while (q--) {
    cnt++;
    int l, r, v;
    cin >> l >> r >> v;
    v ^= last;
    l--;
    r--;
    int res;
    int t = lower_bound(a, a + n, make_pair(v, 0)) - a;
    if (t == n) {
      res = m;
      last = res;
      cout << res << endl;
      continue;
    }
    if (l / ((1 << 13)) == r / ((1 << 13))) {
      res = minimal_solver(l, r, v);
      last = res;
      cout << res << endl;
      continue;
    }
    res = min(minimal_solver(l, (l / ((1 << 13)) + 1) * ((1 << 13)) - 1, v),
              minimal_solver(r / ((1 << 13)) * ((1 << 13)), r, v));
    for (int i = l / ((1 << 13)) + 1; i <= r / ((1 << 13)) - 1; i++)
      res = min(res, s[i][t]);
    last = res;
    cout << res << endl;
  }
}