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;
struct rec {
  int x, key;
} F[230005 / 650][(650 + 5) * 2];
int Ans, n;
int G[230005 / 650][(650 + 5) * 2];
int S[230005 / 650][(650 + 5) * 2], SR[3 * 230005];
int V[230005 / 650][(650 + 5) * 2], VR[3 * 230005];
int L[230005 / 650], Tmp[230005], be[230005];
int ml[230005 / 650], mr[230005 / 650], num[230005 / 650];
int Doit(int t, int num) {
  rec *Ft = F[t];
  for (int i = 1; i <= num; i++) {
    rec Now = Ft[i];
    Tmp[Now.x] += Now.key;
  }
  int Ret = 100000000, now = 0;
  for (int i = ml[t]; i <= mr[t]; i++) {
    now += Tmp[i];
    Tmp[i] = 0;
    if (now < Ret) Ret = now;
  }
  return Ret;
}
int Find(int key) {
  int l = 1, r = num[0], ret = 0;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (VR[mid] < key)
      l = mid + 1, ret = mid;
    else
      r = mid - 1;
  }
  if (!ret) return 0;
  return SR[ret];
}
int Find(int t, int key) {
  int l = 1, r = num[t], ret = 0;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (V[t][mid] < key)
      l = mid + 1, ret = mid;
    else
      r = mid - 1;
  }
  if (!ret) return 0;
  return S[t][ret];
}
int Cnt;
void Query(int t, int key) {
  int l = 1, r = num[t], ret = 0;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (V[t][mid] < key)
      l = mid + 1, ret = mid;
    else
      r = mid - 1;
  }
  if (!ret) return;
  Ans = min(Ans, G[t][ret] + L[t - 1]);
}
void Query(int t, int key, int ll, int rr) {
  rec *Ft = F[t];
  int *Vt = V[t];
  for (int i = 1; i <= num[t]; i++) {
    if (Vt[i] >= key) break;
    rec Now = Ft[i];
    Tmp[Now.x] += Now.key;
  }
  int Ret = 100000000, now = 0;
  for (int i = ml[t]; i <= mr[t]; i++) {
    now += Tmp[i];
    Tmp[i] = 0;
    if (ll <= i && i <= rr)
      if (now < Ret) Ret = now;
  }
  Ans = min(Ans, Ret + L[t - 1]);
}
void Add(int x, int key, int val) {
  if (x > n) return;
  if (x < 1) {
    int t = 0;
    ++num[t];
    SR[num[t]] = SR[num[t] - 1] + key;
    VR[num[t]] = val;
    return;
  }
  int t = be[x];
  ++num[t];
  F[t][num[t]] = (rec){x, key};
  G[t][num[t]] = Doit(t, num[t]);
  S[t][num[t]] = S[t][num[t] - 1] + key;
  V[t][num[t]] = val;
}
struct opt {
  int val, id;
} E[230005];
bool cmp(const opt &i, const opt &j) { return i.val < j.val; }
int main() {
  int m;
  scanf("%d%d", &n, &m);
  int sum = (n + 1) / 650 + 1;
  for (int i = 1; i <= n; i++) scanf("%d", &E[i].val), E[i].id = i;
  sort(E + 1, E + 1 + n, cmp);
  for (int i = 1; i <= sum; i++) ml[i] = max(1, i * 650 - 650);
  for (int i = 1; i <= sum; i++) mr[i] = min(n, i * 650 - 1);
  for (int i = 1; i <= sum; i++)
    for (int j = ml[i]; j <= mr[i]; j++) be[j] = i;
  for (int i = 1; i <= n; i++) {
    Add(E[i].id - m + 1, 1, E[i].val);
    Add(E[i].id + 1, -1, E[i].val);
  }
  int Q_Q;
  scanf("%d", &Q_Q);
  while (Q_Q--) {
    int t, l, r, key;
    scanf("%d%d%d", &l, &r, &key);
    key ^= Ans;
    Ans = 100000000;
    L[0] = Find(key);
    for (int t = 1; t <= be[r]; t++) L[t] = L[t - 1] + Find(t, key);
    if (be[l] == be[r]) {
      t = be[l];
      Query(t, key, l, r);
    } else {
      t = be[l];
      Query(t, key, l, mr[t]);
      t = be[r];
      Query(t, key, ml[t], r);
      for (int d = be[l] + 1; d <= be[r] - 1; d++) Query(d, key);
    }
    printf("%d\n", Ans);
  }
}