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 = 2e5 + 10;
const int M = 500;
int x[N], d[M][M << 1], e[M][M << 1], s[M], t[M];
int n, m, q;
vector<int> O, P[M];
int calc(int L, int R, int X) {
  int a = 0x3f3f3f3f;
  int g = lower_bound(O.begin(), O.end(), X) - O.begin();
  if (!L) a = g;
  for (int i = 0, y; i * M < R; i++) {
    y = lower_bound(P[i].begin(), P[i].end(), X) - P[i].begin() - 1;
    if (y < 0) {
      if (L <= t[i]) a = min(a, g);
      continue;
    }
    if (L <= s[i] && R >= t[i]) {
      a = min(a, g + d[i][y]);
    } else if (max(L, s[i]) <= min(R, t[i])) {
      for (int j = s[i], f = g; j <= t[i]; j++) {
        f -= x[j - 1] < X;
        f += x[j + m - 1] < X;
        if (L <= j && j <= R && a > f) {
          a = f;
        }
      }
    }
    g += e[i][y];
  }
  return a;
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    scanf("%d", x + i);
    if (i < m) O.push_back(x[i]);
  }
  sort(O.begin(), O.end());
  for (int i = 0; i * M + 1 <= n - m; i++) {
    s[i] = i * M + 1, t[i] = min(n - m, (i + 1) * M);
    for (int j = s[i]; j <= t[i]; j++) {
      P[i].push_back(x[j - 1]);
      P[i].push_back(x[j + m - 1]);
    }
    sort(P[i].begin(), P[i].end());
    for (int j = 0; j < P[i].size(); j++) {
      d[i][j] = 0x3f3f3f3f;
      for (int k = s[i]; k <= t[i]; k++) {
        e[i][j] -= x[k - 1] <= P[i][j];
        e[i][j] += x[k + m - 1] <= P[i][j];
        d[i][j] = min(d[i][j], e[i][j]);
      }
    }
  }
  cin >> q;
  for (int l, r, x, a = 0; q--;) {
    scanf("%d %d %d", &l, &r, &x);
    printf("%d\n", a = calc(l - 1, r - 1, x ^ a));
  }
  return 0;
}