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 = 200001;
const int M = 8000001;
unsigned long long tr[M + 10];
int tot = 0;
void decode(unsigned long long t, int &ls, int &rs, int &v) {
  v = t % N;
  t /= N;
  rs = t % M;
  t /= M;
  ls = t;
}
unsigned long long encode(int ls, int rs, int v) {
  unsigned long long t = ls;
  t = t * M + rs;
  return t * N + v;
}
int get_val(int x, bool fg) {
  if (fg) return x;
  if (!x) return 0;
  return tr[x] % N;
}
int update(int p, int l, int r, int ql, int qr) {
  if (l == r) return p + 1;
  int x = ++tot;
  if (l == ql && r == qr) {
    tr[x] = tr[p] + 1;
    return x;
  }
  int mid = (l + r) >> 1;
  int ls, rs, v;
  decode(tr[p], ls, rs, v);
  int add = v - min(get_val(ls, l == mid), get_val(rs, mid + 1 == r));
  if (qr <= mid)
    ls = update(ls, l, mid, ql, qr);
  else if (ql > mid)
    rs = update(rs, mid + 1, r, ql, qr);
  else {
    ls = update(ls, l, mid, ql, mid);
    rs = update(rs, mid + 1, r, mid + 1, qr);
  }
  v = min(get_val(ls, l == mid), get_val(rs, mid + 1 == r)) + add;
  tr[x] = encode(ls, rs, v);
  return x;
}
int query(int p, int l, int r, int ql, int qr) {
  if (!p) return 0;
  if (l == ql && r == qr) return l == r ? p : tr[p] % N;
  int mid = (l + r) >> 1;
  int ls, rs, v;
  decode(tr[p], ls, rs, v);
  int add = v - min(get_val(ls, l == mid), get_val(rs, mid + 1 == r));
  if (qr <= mid) return query(ls, l, mid, ql, qr) + add;
  if (ql > mid) return query(rs, mid + 1, r, ql, qr) + add;
  return min(query(ls, l, mid, ql, mid), query(rs, mid + 1, r, mid + 1, qr)) +
         add;
}
pair<int, int> a[N];
int root[N];
int n, m;
int Find(int v) {
  int l = 0, r = n - 1, res = -1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (a[mid].first < v) {
      res = mid;
      l = mid + 1;
    } else
      r = mid - 1;
  }
  return res + 1;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i].first);
    a[i].second = i + 1;
  }
  sort(a, a + n);
  for (int i = 1; i <= n; ++i) {
    int l = max(1, a[i - 1].second - m + 1);
    int r = min(n - m + 1, a[i - 1].second);
    root[i] = update(root[i - 1], 1, n - m + 1, l, r);
  }
  int q, ans = 0;
  scanf("%d", &q);
  while (q--) {
    int l, r, v;
    scanf("%d%d%d", &l, &r, &v);
    v ^= ans;
    int p = Find(v);
    ans = query(root[p], 1, n - m + 1, l, r);
    printf("%d\n", ans);
  }
  return 0;
}