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 N = 200100;
const int M = 500;
vector<pair<int, int> > ope[N], add[M];
vector<int> lis[M], Max[M];
int val[N], idx[N];
int n, m;
void init_() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) scanf("%d", val + i);
  for (int i = 1; i <= n; i++) idx[i] = i / M + 1;
  for (int i = 0; i <= n; i++) lis[idx[i]].push_back(i);
  for (int i = 1; i <= n; i++) {
    int l = max(0, i + 1 - m), r = i + 1;
    ope[l].push_back(pair<int, int>(val[i], 1));
    if (r <= n) ope[r].push_back(pair<int, int>(val[i], -1));
    add[idx[l]].push_back(pair<int, int>(val[i], 1));
    if (r <= n) add[idx[r]].push_back(pair<int, int>(val[i], -1));
  }
  sort(add[0].begin(), add[0].end(), greater<pair<int, int> >());
  for (int j = 1; j <= (int)add[0].size() - 1; j++)
    add[0][j].second += add[0][j - 1].second;
  for (int i = 1; i <= idx[n]; i++) {
    sort(add[i].begin(), add[i].end(), greater<pair<int, int> >());
    for (int j = 0; j <= (int)add[i].size() - 1; j++) {
      int res = 0, ans = 0;
      for (int k : lis[i]) {
        for (pair<int, int> l : ope[k])
          if (l.first >= add[i][j].first) res += l.second;
        ans = max(ans, res);
      }
      add[i][j].second = res;
      Max[i].push_back(ans);
    }
  }
}
int query(int l, int r, int q) {
  int x = idx[l], y = idx[r];
  int base = 0, ans = 0;
  for (int i = 0; i <= x - 1; i++) {
    auto ii =
        lower_bound(add[i].begin(), add[i].end(),
                    pair<int, int>(q, -1000000000), greater<pair<int, int> >());
    if (ii != add[i].begin()) base += (ii - 1)->second;
  }
  for (int k : lis[x]) {
    for (pair<int, int> l : ope[k])
      if (l.first >= q) base += l.second;
    if (l <= k && k <= r) ans = max(ans, base);
  }
  for (int i = x + 1; i <= y - 1; i++) {
    auto ii =
        lower_bound(add[i].begin(), add[i].end(),
                    pair<int, int>(q, -1000000000), greater<pair<int, int> >());
    if (ii != add[i].begin()) {
      ans = max(ans, base + *(ii - add[i].begin() + Max[i].begin() - 1));
      base += (ii - 1)->second;
    }
  }
  if (y != x) {
    for (int k : lis[y]) {
      for (pair<int, int> l : ope[k])
        if (l.first >= q) base += l.second;
      if (k <= r) ans = max(ans, base);
    }
  }
  return ans;
}
int main() {
  init_();
  int s;
  cin >> s;
  int ans = 0;
  while (s--) {
    int l, r, q;
    scanf("%d%d%d", &l, &r, &q);
    q ^= ans;
    ans = m - query(l, r, q);
    printf("%d\n", ans);
  }
  return 0;
}