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;
bool debug = 1;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
long long ln, lk, lm;
int a[200002], S;
vector<int> v, val[450];
int mn[450][450 * 2], sum[450][450 * 2];
int cal(int l, int r, int x) {
  int ans = (1 << 30);
  int now = lower_bound(v.begin(), v.end(), x) - v.begin();
  for (int i = 0; i * S < n - m + 1 && i * S < r; i++) {
    int st = i * S;
    int ed = min(st + S, n - m + 1);
    k = lower_bound(val[i].begin(), val[i].end(), x) - val[i].begin() - 1;
    if (k < 0) {
      if (max(l, st) < min(r, ed)) ans = min(ans, now);
      continue;
    }
    if (l <= st && ed <= r) {
      ans = min(ans, now + mn[i][k]);
      now += sum[i][k];
    } else {
      if (max(l, st) < min(r, ed)) {
        for (int j = st; j < ed; j++) {
          if (j > 0 && a[j - 1] <= val[i][k]) now--;
          if (a[j - 1 + m] <= val[i][k]) now++;
          if (l <= j && j < r) ans = min(ans, now);
        }
      } else
        now += sum[i][k];
    }
  }
  return ans;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
  }
  for (int(i) = 0; (i) < (int)(m - 1); (i)++) v.push_back(a[i]);
  sort(v.begin(), v.end());
  S = sqrt(n);
  for (int i = 0; i * S < n - m + 1; i++) {
    int st = i * S;
    int ed = min(st + S, n - m + 1);
    for (int j = st; j < ed; j++) {
      if (j > 0) val[i].push_back(a[j - 1]);
      val[i].push_back(a[j + m - 1]);
    }
    sort(val[i].begin(), val[i].end());
    val[i].resize(unique(val[i].begin(), val[i].end()) - val[i].begin());
    for (int(k) = 0; (k) < (int)(val[i].size()); (k)++) {
      mn[i][k] = (1 << 30);
      for (int j = st; j < ed; j++) {
        if (j > 0 && a[j - 1] <= val[i][k]) sum[i][k]--;
        if (a[j - 1 + m] <= val[i][k]) sum[i][k]++;
        mn[i][k] = min(mn[i][k], sum[i][k]);
      }
    }
  }
  int q;
  scanf("%d", &q);
  for (int l, r, x, i = 0, ans = 0; i < q; i++) {
    scanf("%d%d%d", &l, &r, &x);
    x ^= ans;
    ans = cal(l - 1, r, x);
    printf("%d\n", ans);
  }
  return 0;
}