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>
const int maxn = 200001, maxm = 451, maxc = 1351;
int n, m, q, a[maxn], ord[maxn];
int sz, tot, cnt[maxm], pos[maxm][maxc];
int qL[maxn], qR[maxn], mx[maxm][maxc], fir[maxm][maxc];
int seq[maxn], dt[maxc], ans;
bool cmp(int const &x, int const &y) { return a[x] > a[y]; }
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", a + i);
    ord[i] = i;
  }
  std::sort(ord + 1, ord + n + 1, cmp);
  sz = (int)ceil(sqrt(n));
  for (int i = 1; i <= n; i += sz, ++tot) {
    int L = i, R = std::min(i + sz - 1, n);
    cnt[tot] = 0;
    for (int j = 1; j <= n; j += sz) pos[tot][cnt[tot]++] = j;
    pos[tot][cnt[tot]++] = n + 1;
    for (int j = L; j <= R; ++j) {
      pos[tot][cnt[tot]++] = (qL[j] = std::max(1, ord[j] - m + 1));
      pos[tot][cnt[tot]++] = (qR[j] = ord[j] + 1);
    }
    std::sort(pos[tot], pos[tot] + cnt[tot]);
    cnt[tot] = std::unique(pos[tot], pos[tot] + cnt[tot]) - pos[tot];
    memset(dt, 0, cnt[tot] * sizeof(int));
    for (int j = L; j <= R; ++j) {
      qL[j] = std::lower_bound(pos[tot], pos[tot] + cnt[tot], qL[j]) - pos[tot];
      qR[j] = std::lower_bound(pos[tot], pos[tot] + cnt[tot], qR[j]) - pos[tot];
      ++dt[qL[j]];
      --dt[qR[j]];
    }
    for (int j = 0; j + 1 < cnt[tot]; ++j) {
      int pL = pos[tot][j], pR = pos[tot][j + 1];
      for (fir[tot][j] = mx[tot][j] = seq[pL++]; pL < pR; ++pL)
        if (mx[tot][j] < seq[pL]) mx[tot][j] = seq[pL];
      for (pL = pos[tot][j]; pL < pR; ++pL) seq[pL] += dt[j];
      dt[j + 1] += dt[j];
    }
  }
  scanf("%d", &q);
  while (q--) {
    int L, R, idx;
    scanf("%d%d%d", &L, &R, a + 0);
    a[0] ^= ans;
    idx = std::upper_bound(ord + 1, ord + n + 1, 0, cmp) - ord - 1;
    int blk = std::min(idx / sz, tot - 1);
    memset(dt, 0, cnt[blk] * sizeof(int));
    for (int i = blk * sz + 1; i <= idx; ++i) {
      ++dt[qL[i]];
      --dt[qR[i]];
    }
    ans = 0;
    for (int i = 0; i + 1 < cnt[blk]; ++i) {
      dt[i + 1] += dt[i];
      if (L <= pos[blk][i] && pos[blk][i + 1] <= R + 1)
        ans = std::max(ans, mx[blk][i] + dt[i]);
      else if (pos[blk][i] <= R && L < pos[blk][i + 1])
        for (int j = pos[blk][i], val = fir[blk][i] + dt[i];
             j < pos[blk][i + 1]; ++j) {
          if (j > R)
            break;
          else if (j >= L)
            ans = std::max(ans, val);
          val -= (a[j] >= a[0]);
          val += (a[j + m] >= a[0]);
        }
    }
    printf("%d\n", ans = m - ans);
  }
  return 0;
}