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 unsigned long long N = 8e6, T = 200000;
struct hjt {
  unsigned long long msk[8050000], sum;
  int rt[200002], sz;
  unsigned long long code(int lp, int rp, int val, int lazy) {
    return (1ull * lp * N * T + 1ull * rp * T + 1ull * val + 1ull * lazy);
  }
  void decode(unsigned long long mskk, int &lp, int &rp, int &val, int &lazy,
              int l, int r, int mid) {
    lp = mskk / N / T;
    rp = (mskk / T) % N;
    sum = mskk % T;
    val = max((l == mid ? lp : msk[lp] % T), (mid + 1 == r ? rp : msk[rp] % T));
    lazy = sum - val;
  }
  int update(int pre, int beg, int en, int lp, int rp) {
    if (lp > en || rp < beg) return pre;
    if (lp == rp) return pre + 1;
    int pos = ++sz;
    if (lp >= beg && rp <= en) {
      msk[pos] = msk[pre] + 1;
      return pos;
    }
    int ls, rs, val, lazy, mid = (lp + rp) >> 1;
    decode(msk[pre], ls, rs, val, lazy, lp, rp, mid);
    ls = update(ls, beg, en, lp, mid);
    rs = update(rs, beg, en, mid + 1, rp);
    msk[pos] = code(
        ls, rs,
        max((lp == mid ? ls : msk[ls] % T), (mid + 1 == rp ? rs : msk[rs] % T)),
        lazy);
    return pos;
  }
  int query(int beg, int en, int lp, int rp, int node) {
    if (!node) return 0;
    if (lp > en || rp < beg) return 0;
    if (lp == rp) return node;
    if (lp >= beg && rp <= en) return msk[node] % T;
    int mid = (lp + rp) >> 1, ls, rs, val, lazy;
    decode(msk[node], ls, rs, val, lazy, lp, rp, mid);
    return max(query(beg, en, lp, mid, ls), query(beg, en, mid + 1, rp, rs)) +
           lazy;
  }
} tree;
int n, m, a[200002], b[200002], l, r, x, q, ans, L, R;
bool cmp(int i, int j) { return a[i] > a[j]; }
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) b[i] = i;
  sort(b + 1, b + n + 1, cmp);
  for (int i = 1; i <= n; i++) {
    L = max(1, b[i] - m + 1);
    R = b[i];
    tree.rt[i] = tree.update(tree.rt[i - 1], L, R, 1, n - m + 1);
  }
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d%d", &l, &r, &x);
    x ^= ans;
    L = 1;
    R = n;
    while (L <= R) {
      int mid = (L + R) >> 1;
      if (a[b[mid]] >= x)
        L = mid + 1;
      else
        R = mid - 1;
    }
    ans = tree.query(l, r, 1, n - m + 1, tree.rt[R]);
    ans = m - ans;
    printf("%d\n", ans);
  }
  return 0;
}