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 = 200010, M = 510;
int n, m, lis[N], a[N], bc, b[N], bl[N], br[N], p[N], cnt, v[N];
int f[M][M], la[N], w[N], st[M][M], pre[N], suf[N], ed[N];
inline bool comp(int i, int j) { return a[i] > a[j]; }
inline void Modify(int k, int l, int r) {
  if (b[l] == b[r]) {
    for (int i = l; i <= r; i++) w[i]++;
    for (int i = bl[b[l]]; i <= br[b[l]]; i++) pre[k] = max(pre[k], w[i]);
    return;
  }
  for (int i = l; i <= br[b[l]]; i++) w[i]++;
  for (int i = bl[b[l]]; i <= br[b[l]]; i++) pre[k] = max(pre[k], w[i]);
  for (int i = b[l] + 1; i < b[r]; i++) la[i]++;
  for (int i = bl[b[r]]; i <= r; i++) w[i]++;
  for (int i = bl[b[r]]; i <= br[b[r]]; i++) suf[k] = max(suf[k], w[i]);
}
inline void rec(int k) {
  for (int i = 1; i <= cnt; i++) {
    for (int j = bl[i]; j <= br[i]; j++) f[k][i] = max(f[k][i], w[j] += la[i]);
    st[k][i] = w[bl[i]];
    la[i] = 0;
  }
}
inline int qry(int l, int r, int k, int x) {
  int now = v[k], ret = 0;
  for (int i = bl[k]; i < l; i++) now += (a[i + m] >= x) - (a[i] >= x);
  for (int i = l; i <= r; i++)
    ret = max(ret, now), now += (a[i + m] >= x) - (a[i] >= x);
  return ret;
}
int main() {
  scanf("%d%d", &n, &m);
  bc = sqrt(n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), lis[i] = a[i], p[i] = i;
  sort(lis + 1, lis + n + 1);
  int tp = unique(lis + 1, lis + n + 1) - lis - 1, Q, ans = 0;
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(lis + 1, lis + tp + 1, a[i]) - lis;
  for (int i = 1, t; i <= n; i++)
    t = b[i] = (i - 1) / bc + 1, bl[t] = bl[t] ? bl[t] : i, br[t] = i;
  sort(p + 1, p + n + 1, comp);
  cnt = b[n];
  for (int i = 1; i <= n; i++) {
    Modify(i, max(1, p[i] - m + 1), p[i]);
    if (b[i] != b[i + 1]) rec(b[i]), ed[b[i]] = a[p[i]];
  }
  cin >> Q;
  while (Q--) {
    int l, r, x, t = 1;
    scanf("%d%d%d", &l, &r, &x);
    x = lower_bound(lis + 1, lis + tp + 1, x ^ ans) - lis;
    while (t < cnt && ed[t] >= x) t++;
    for (int i = 1; i <= cnt; i++)
      w[i] = f[t - 1][i], v[i] = st[t - 1][i], la[i] = 0;
    for (int i = bl[t]; i <= br[t] && a[p[i]] >= x; i++) {
      int L = max(1, p[i] - m + 1), R = p[i], A = b[L], B = b[R];
      if (A == B)
        w[A] = pre[i];
      else {
        w[A] = pre[i];
        w[B] = suf[i];
        la[A + 1]++;
        la[B]--;
      }
      if (L <= bl[b[l]] && bl[b[l]] <= R) v[b[l]]++;
      if (b[l] != b[r] && L <= bl[b[r]] && bl[b[r]] <= R) v[b[r]]++;
    }
    for (int i = 1; i <= cnt; i++) la[i] += la[i - 1];
    int A = b[l], B = b[r];
    if (A == B)
      ans = qry(l, r, A, x);
    else {
      ans = max(qry(l, br[A], A, x), qry(bl[B], r, B, x));
      for (int i = A + 1; i < B; i++) ans = max(ans, la[i] + w[i]);
    }
    ans = m - ans;
    printf("%d\n", ans);
  }
  return 0;
}