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 = 200003;
const int NBLK = 454;
const int SZBLK = MAXN / NBLK + 3;
int n, m, a[MAXN];
int n0;
vector<int> all[NBLK], mpos[NBLK], sum[NBLK];
int size[NBLK];
void makeblk(int l, int r, vector<int> &all, vector<int> &mpos,
             vector<int> &sum, int &size) {
  all.push_back(0);
  for (int i = l; i < r; ++i) {
    int mn = a[i], mx = a[i + m];
    if (mn > mx) swap(mn, mx);
    all.push_back(mn + 1);
    all.push_back(mx + 1);
  }
  sort(all.begin(), all.end());
  all.erase(unique(all.begin(), all.end()), all.end());
  size = all.size();
  mpos.resize(size);
  sum.resize(size);
  for (int i = 0; i < size; ++i) {
    int mp = 0, sm = 0;
    int alli = all[i];
    for (int j = l; j < r; ++j)
      if (a[j] < alli && alli <= a[j + m]) {
        --sm;
        mp = min(mp, sm);
      } else if (a[j + m] < alli && alli <= a[j])
        ++sm;
    sum[i] = sm;
    mpos[i] = mp;
  }
}
int init[MAXN];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
  for (int i = 0; i < m; ++i) init[i] = a[i];
  sort(init, init + m);
  n0 = n - m + 1;
  for (int i = 0, j = 0; i < n0; i += SZBLK, ++j)
    makeblk(i, min(i + SZBLK, n0), all[j], mpos[j], sum[j], size[j]);
  int Q;
  scanf("%d", &Q);
  int lastans = 0;
  while (Q--) {
    int l, r, x;
    scanf("%d%d%d", &l, &r, &x);
    x ^= lastans;
    --l;
    int bl = l / SZBLK, br = (r - 1) / SZBLK;
    int sm = lower_bound(init, init + m, x) - init;
    for (int i = 0; i < bl; ++i) {
      int pos =
          upper_bound(all[i].begin(), all[i].end(), x) - all[i].begin() - 1;
      sm += sum[i][pos];
    }
    int ans = INT_MAX;
    if (bl == br)
      for (int i = bl * SZBLK; i < r; ++i) {
        if (i >= l) ans = min(ans, sm);
        if (a[i] < x && x <= a[i + m])
          --sm;
        else if (a[i + m] < x && x <= a[i])
          ++sm;
      }
    else {
      for (int i = bl * SZBLK; i < (bl + 1) * SZBLK; ++i) {
        if (i >= l) ans = min(ans, sm);
        if (a[i] < x && x <= a[i + m])
          --sm;
        else if (a[i + m] < x && x <= a[i])
          ++sm;
      }
      for (int i = bl + 1; i < br; ++i) {
        int pos =
            upper_bound(all[i].begin(), all[i].end(), x) - all[i].begin() - 1;
        ans = min(ans, sm + mpos[i][pos]);
        sm += sum[i][pos];
      }
      for (int i = br * SZBLK; i < r; ++i) {
        ans = min(ans, sm);
        if (a[i] < x && x <= a[i + m])
          --sm;
        else if (a[i + m] < x && x <= a[i])
          ++sm;
      }
    }
    printf("%d\n", lastans = ans);
  }
  return 0;
}