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;
unsigned long long t[8000005];
struct node {
  int x, y;
} tt[200005];
int ans, i, A, B, C, n, m, Q, cnt, root[200005], L, R, mid;
int cmp(node i, node j) { return i.x > j.x; }
void work(unsigned long long A, int &B, int &C) {
  A /= 200001;
  C = A % 8000001;
  A /= 8000001;
  B = A % 8000001;
}
unsigned long long WORK(unsigned long long A, unsigned long long B,
                        unsigned long long C) {
  A *= 8000001;
  A *= 200001;
  B *= 200001;
  return A + B + C;
}
void Update(int &A, int &B, int l, int r, int L, int R) {
  if (l == r) {
    B = A + 1;
    return;
  }
  if (!B) B = ++cnt;
  int mid = (l + r) / 2, llB, rrB, llA, rrA;
  work(t[B], llB, rrB);
  work(t[A], llA, rrA);
  if (l == L && r == R) {
    if (!llB) llB = llA;
    if (!rrB) rrB = rrA;
    int D = t[A] % 200001 - max(mid == l ? llA : t[llA] % 200001,
                                mid + 1 == r ? rrA : t[rrA] % 200001);
    t[B] = WORK(llB, rrB,
                max(mid == l ? llB : t[llB] % 200001,
                    mid + 1 == r ? rrB : t[rrB] % 200001) +
                    D + 1);
    return;
  }
  int D = t[A] % 200001 - max(mid == l ? llA : t[llA] % 200001,
                              mid + 1 == r ? rrA : t[rrA] % 200001);
  if (L <= mid) Update(llA, llB, l, mid, L, min(mid, R));
  if (R > mid) Update(rrA, rrB, mid + 1, r, max(mid + 1, L), R);
  if (!llB) llB = llA;
  if (!rrB) rrB = rrA;
  t[B] = WORK(llB, rrB,
              max(mid == l ? llB : t[llB] % 200001,
                  mid + 1 == r ? rrB : t[rrB] % 200001) +
                  D);
}
int work2(int A, int l, int r, int L, int R) {
  if (l == L && r == R) return l == r ? A : t[A] % 200001;
  int mid = (l + r) / 2, llA, rrA, p = 0, q = 0;
  work(t[A], llA, rrA);
  int D = t[A] % 200001 - max(mid == l ? llA : t[llA] % 200001,
                              mid + 1 == r ? rrA : t[rrA] % 200001);
  if (L <= mid) p = work2(llA, l, mid, L, min(mid, R));
  if (R > mid) q = work2(rrA, mid + 1, r, max(mid + 1, L), R);
  return max(p, q) + D;
}
int main() {
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) {
    scanf("%d", &tt[i].x);
    tt[i].y = i;
  }
  sort(tt + 1, tt + n + 1, cmp);
  for (i = 1; i <= n; i++)
    Update(root[i - 1], root[i], 1, n - m + 1, max(1, tt[i].y - m + 1),
           min(n - m + 1, tt[i].y));
  scanf("%d", &Q);
  while (Q--) {
    scanf("%d%d%d", &A, &B, &C);
    C ^= ans;
    L = 1;
    R = n;
    mid = (L + R) / 2;
    while (L <= R) {
      if (tt[mid].x < C) {
        R = mid - 1;
        mid = (L + R) / 2;
      } else {
        L = mid + 1;
        mid = (L + R) / 2;
      }
    }
    if (!R) {
      ans = m;
      printf("%d\n", ans);
      continue;
    }
    ans = m - work2(root[R], 1, n - m + 1, A, B);
    printf("%d\n", ans);
  }
  return 0;
}