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;
inline void read(int &x) {
  x = 0;
  int ch = getchar();
  int sign = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') sign = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
  x = x * sign;
}
const int INF = 0x66CCFF;
const int maxn = 200010;
const int maxm = 480;
int A[maxn];
pair<int, int> B[maxn];
int n, len;
int m, k;
int Pre[maxn];
int Add[maxm];
int Max[maxm], BMax[maxm][maxm];
int V[maxn], BVal[maxm][maxm];
int ResMax[maxm][maxm << 1];
inline void Pretreat() {
  static int V[maxn];
  m = (int)sqrt(n + 0.5);
  k = n / m + (n % m != 0);
  register int i, j;
  for (i = 1; i <= n; i++) Pre[i] = (i - 1) / m + 1;
  for (i = 1; i <= n; i++) {
    if (i == ((Pre[i] - 1) * m + 1)) {
      for (j = 1; j <= n; j++) V[j] += Add[Pre[j]];
      for (j = 1; j <= k; j++) {
        Max[j] += Add[j];
        BMax[Pre[i]][j] = Max[j];
        BVal[Pre[i]][j] = V[(j - 1) * m + 1];
        Add[j] = 0;
      }
    }
    int r = B[i].second, l = (1 > r - len + 1 ? 1 : r - len + 1);
    int L = ((Pre[l] * m) < r ? (Pre[l] * m) : r),
        R = (L + 1 > ((Pre[r] - 1) * m + 1) ? L + 1 : ((Pre[r] - 1) * m + 1));
    int &ML = Max[Pre[l]], &MR = Max[Pre[r]];
    for (j = l; j <= L; j++) {
      V[j]++;
      if (ML < V[j]) ML = V[j];
    }
    for (j = R; j <= r; j++) {
      V[j]++;
      if (MR < V[j]) MR = V[j];
    }
    for (j = Pre[l] + 1; j < Pre[r]; j++) Add[j]++;
    int id = i - ((Pre[i] - 1) * m + 1);
    for (j = 0; j < 2; j++) {
      int Now = Pre[j ? r : l];
      ResMax[Pre[i]][id + j * m] = (Max[Now]) * k + Now - 1;
    }
  }
}
inline int find(int v) {
  int L = 1, R = n;
  while (L < R) {
    int mid = (L + R) >> 1;
    if (B[mid].first <= v)
      L = mid + 1;
    else
      R = mid;
  }
  return B[L].first <= v ? L + 1 : L;
}
inline int Query(int l, int r, int ST, int pos, int qv) {
  register int i, cnt;
  int STVal = ((Pre[l] - 1) * m + 1);
  cnt = BVal[Pre[ST]][Pre[l]];
  for (i = ST; i <= pos; i++)
    if (STVal <= B[i].second &&
        STVal >= (1 > B[i].second - len + 1 ? 1 : B[i].second - len + 1))
      cnt++;
  for (; STVal < l; STVal++) {
    cnt -= (A[STVal] >= qv);
    cnt += (A[STVal + len] >= qv);
  }
  int Ans = 0;
  for (i = l; i <= r; i++) {
    if (cnt > Ans) Ans = cnt;
    cnt -= (A[i] >= qv);
    cnt += (A[i + len] >= qv);
  }
  return Ans;
}
int main() {
  read(n), read(len);
  for (int i = 1; i <= n; i++) read(A[i]), B[i] = make_pair(-A[i], i);
  sort(B + 1, B + 1 + n);
  Pretreat();
  int q, Ans = 0;
  read(q);
  while (q--) {
    int ql, qr, qv;
    read(ql), read(qr), read(qv);
    qv ^= Ans;
    if (-qv >= B[n].first)
      Ans = len;
    else if (-qv < B[1].first)
      Ans = 0;
    else {
      register int i;
      int pos = find(-qv) - 1;
      int BLC = Pre[pos];
      for (i = 1; i <= k; i++) Max[i] = BMax[BLC][i], Add[i] = 0;
      int ST = ((Pre[pos] - 1) * m + 1);
      for (i = ST; i <= pos; i++) {
        int r = B[i].second, l = (1 > r - len + 1 ? 1 : r - len + 1);
        if (Pre[l] != Pre[r]) Add[Pre[l] + 1]++, Add[Pre[r]]--;
        for (int j = 0; j < 2; j++)
          Max[ResMax[BLC][i - ST + j * m] % k + 1] =
              ResMax[BLC][i - ST + j * m] / k;
      }
      for (i = 1; i <= k; i++) Add[i] += Add[i - 1];
      Ans = 0;
      int L = ((Pre[ql] * m) < qr ? (Pre[ql] * m) : qr),
          R = (L + 1 > ((Pre[qr] - 1) * m + 1) ? L + 1
                                               : ((Pre[qr] - 1) * m + 1));
      for (i = Pre[ql] + 1; i < Pre[qr]; i++)
        Ans = (Ans > Max[i] + Add[i] ? Ans : Max[i] + Add[i]);
      Ans = (Ans > Query(ql, L, ST, pos, qv) ? Ans : Query(ql, L, ST, pos, qv));
      Ans = (Ans > Query(R, qr, ST, pos, qv) ? Ans : Query(R, qr, ST, pos, qv));
    }
    Ans = len - Ans;
    printf("%d\n", Ans);
  }
  return 0;
}