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 int maxN = 402000;
const int maxB = 510;
const int inf = 2000000000;
int n, m, bcnt;
int Seq[maxN], Srt[maxN], B[maxN], Bl[maxN], Br[maxN];
int Label[maxN], Val[maxN];
int Lkey[maxB][maxB], Mn[maxB][maxB], Lmn[maxN], Rmn[maxN];
int Rgmn[maxN], Sm[maxN], Lft[maxN];
pair<int, int> Pr[maxN];
int Query(int l, int r, int x);
int main() {
  register int i, j, l, r;
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; ++i) scanf("%d", &Seq[i]), Pr[i] = make_pair(Seq[i], i);
  sort(&Pr[1], &Pr[n + 1]);
  for (i = 1; i <= n; ++i) Srt[i] = Pr[i].first;
  Srt[0] = -inf;
  int Block = sqrt(n);
  bcnt = (n - 1) / Block + 1;
  for (i = 1; i <= n; ++i) {
    B[i] = (i - 1) / Block + 1;
    Br[B[i]] = i;
    if (!Bl[B[i]]) Bl[B[i]] = i;
  }
  for (i = 1; i <= n; ++i) {
    l = max(Pr[i].second - m + 1, 1);
    r = Pr[i].second;
    if (B[l] == B[r])
      for (j = l; j <= r; ++j) ++Val[j];
    else {
      for (j = l; j <= Br[B[l]]; ++j) ++Val[j];
      for (j = Bl[B[r]]; j <= r; ++j) ++Val[j];
      for (j = B[l] + 1; j < B[r]; ++j) ++Label[j];
    }
    Lmn[i] = inf;
    for (j = Bl[B[l]]; j <= Br[B[l]]; ++j) Lmn[i] = min(Lmn[i], Val[j]);
    Rmn[i] = inf;
    for (j = Bl[B[r]]; j <= Br[B[r]]; ++j) Rmn[i] = min(Rmn[i], Val[j]);
    if (B[i] != B[i + 1]) {
      int b = B[i];
      for (j = 1; j <= n; ++j) Val[j] += Label[B[j]];
      for (j = 1; j <= bcnt; ++j)
        Label[j] = 0, Mn[b][j] = inf, Lkey[b][j] = Val[Bl[j]];
      for (j = 1; j <= n; ++j) Mn[b][B[j]] = min(Mn[b][B[j]], Val[j]);
    }
  }
  int Q, lstans = 0;
  scanf("%d", &Q);
  while (Q--) {
    int nx;
    scanf("%d%d%d", &l, &r, &nx);
    nx ^= lstans;
    int cl = 1, cr = n, p = 0;
    while (cl <= cr) {
      int mid = (cl + cr) >> 1;
      if (Pr[mid].first <= nx - 1)
        p = mid, cl = mid + 1;
      else
        cr = mid - 1;
    }
    if (p == 0) {
      printf("%d\n", lstans = 0);
      continue;
    }
    int stb = B[p];
    for (i = 1; i <= bcnt; ++i)
      Sm[i] = 0, Lft[i] = Lkey[stb - 1][i], Rgmn[i] = Mn[stb - 1][i];
    for (i = Bl[stb]; i <= p; ++i) {
      int pl = max(Pr[i].second - m + 1, 1), pr = Pr[i].second;
      Rgmn[B[pl]] = Lmn[i];
      Rgmn[B[pr]] = Rmn[i];
      if (B[pl] < B[pr]) ++Sm[B[pl] + 1], --Sm[B[pr]];
      if (pl <= Bl[B[l]] && Bl[B[l]] <= pr) ++Lft[B[l]];
      if (pl <= Bl[B[r]] && Bl[B[r]] <= pr && B[l] != B[r]) ++Lft[B[r]];
    }
    for (i = 1; i <= bcnt; ++i) Sm[i] += Sm[i - 1], Rgmn[i] += Sm[i];
    if (B[l] == B[r])
      lstans = Query(l, r, nx - 1);
    else {
      lstans = min(Query(l, Br[B[l]], nx - 1), Query(Bl[B[r]], r, nx - 1));
      for (int i = B[l] + 1; i < B[r]; i++) lstans = min(lstans, Rgmn[i]);
    }
    printf("%d\n", lstans);
  }
  return 0;
}
int Query(int l, int r, int x) {
  int val = Lft[B[l]];
  for (int i = Bl[B[l]] + 1; i <= l; i++)
    val += (Seq[i + m - 1] <= x) - (Seq[i - 1] <= x);
  int ret = val;
  for (int i = l + 1; i <= r; i++)
    val += (Seq[i + m - 1] <= x) - (Seq[i - 1] <= x), ret = min(ret, val);
  return ret;
}