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;
int i, j, k, n, m, q, an;
int a[200010], ma[200010][2], zhi[500][500], tma[500], ge[200010], id[200010],
    cov[500], L[200010], R[200010], fu[500][500], yi[500][500];
inline bool cc1(const int &A, const int &B) { return a[A] < a[B]; }
inline int get(int x) { return x / 500; }
inline int xia(int x) { return (x / 500 + 1) * 500 - 1; }
inline int qian(int x) { return x / 500 * 500; }
inline void pre() {
  for (i = 0; i <= n; i++) id[i] = i;
  sort(id, id + n + 1, cc1);
  for (i = 0; i <= n; i++) {
    int A = id[i];
    int wei = get(i);
    if (i % 500 == 0) {
      for (j = 0; j <= 500 - 1; j++) {
        zhi[wei][j] = tma[j];
        fu[wei][j] = cov[j];
        yi[wei][j] = ge[j * 500] + cov[j];
      }
    }
    L[i] = R[i] = -1;
    for (j = max(0, A - m + 1); j <= A;) {
      int _ = get(j);
      if (j % 500 == 0 && j + 500 - 1 <= A) {
        cov[_]++;
        if (L[i] < 0) L[i] = _;
        R[i] = _;
        j += 500;
      } else {
        int f = _ == get(A) ? 1 : 0;
        ge[j]++;
        tma[_] = max(tma[_], ge[j]);
        ma[i][f] = max(ma[i][f], ge[j]);
        j++;
      }
    }
  }
}
inline int find(int x) {
  int l = 0, r = n, mid;
  for (; l <= r;) {
    mid = (l + r) / 2;
    if (a[id[mid]] <= x)
      l = mid + 1;
    else
      r = mid - 1;
  }
  return l - 1;
}
inline void work(int l, int r, int x) {
  int shu = find(x), i, j;
  int wei = get(shu);
  int zuo = get(l) + 1, you = get(r) - 1;
  an = 0;
  for (i = 0; i <= 500 - 1; i++) tma[i] = 0;
  for (i = qian(shu); i <= shu; i++) {
    if (L[i] < 0) continue;
    tma[L[i]]++, tma[R[i] + 1]--;
  }
  for (i = 1; i <= 500 - 1; i++) tma[i] += tma[i - 1];
  for (i = 0; i <= 500 - 1; i++) tma[i] += fu[wei][i];
  for (i = qian(shu); i <= shu; i++) {
    int A = id[i];
    int le = max(0, A - m + 1), ri = A;
    if (get(le) >= zuo && get(le) <= you) an = max(an, ma[i][0] + tma[get(le)]);
    if (get(ri) >= zuo && get(ri) <= you) an = max(an, ma[i][1] + tma[get(ri)]);
  }
  for (i = zuo; i <= you; i++) an = max(an, tma[i] + zhi[wei][i]);
  {
    int s;
    j = qian(l);
    s = yi[wei][get(j)];
    for (i = qian(shu); i <= shu; i++) {
      int A = id[i];
      int le = max(0, A - m + 1), ri = A;
      if (le <= j && j <= ri) s++;
    }
    j += m;
    for (i = qian(l); i <= xia(l); i++) {
      for (; j <= n && i + m - 1 >= j; j++) s += a[j] <= x;
      if (i >= l && i <= r) an = max(an, s);
      s -= a[i] <= x;
    }
  }
  {
    int s;
    j = qian(r);
    s = yi[wei][get(j)];
    for (i = qian(shu); i <= shu; i++) {
      int A = id[i];
      int le = max(0, A - m + 1), ri = A;
      if (le <= j && j <= ri) s++;
    }
    j += m;
    for (i = qian(r); i <= xia(r); i++) {
      for (; j <= n && i + m - 1 >= j; j++) s += a[j] <= x;
      if (i >= l && i <= r) an = max(an, s);
      s -= a[i] <= x;
    }
  }
  an = m - an;
  printf("%d\n", an);
}
int main() {
  scanf("%d%d", &n, &m);
  n--;
  for (i = 0; i <= n; i++) scanf("%d", &a[i]), a[i] *= -1;
  pre();
  scanf("%d", &q);
  for (i = 1; i <= q; i++) {
    int l, r, x;
    scanf("%d%d%d", &l, &r, &x);
    x ^= an;
    l--, r--;
    work(l, r, -x);
  }
  return 0;
}