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 limite = 1000000;
const int base = 450;
struct segmento {
  int pos, sol, solmax, anyade, acumulado;
};
struct accion {
  int val, le, ri;
  accion() {}
  accion(int inval, int inle, int inri) {
    val = inval;
    le = inle;
    ri = inri;
  }
};
int a[limite];
int n, m;
int calcula(int q, int le, int ri, vector<segmento> &vseg,
            vector<accion> &vacc) {
  for (int i = 0; i < int(vseg.size()); i++) vseg[i].anyade = 0;
  for (int i = 0; i < int(vacc.size()) and vacc[i].val < q; i++) {
    vseg[vacc[i].le].anyade--;
    vseg[vacc[i].ri].anyade++;
  }
  vseg[0].acumulado = vseg[0].anyade;
  for (int i = 1; i < int(vseg.size()); i++)
    vseg[i].acumulado = vseg[i - 1].acumulado + vseg[i].anyade;
  int sol = 0;
  for (int i = 0; i < int(vseg.size()) - 1; i++) {
    segmento &s = vseg[i];
    int segini = s.pos;
    int segtope = vseg[i + 1].pos;
    if (le <= segini and segtope <= ri + 1)
      sol = max(sol, s.solmax + s.acumulado);
    else if (le < segtope and segini <= ri) {
      int lef = max(le, segini);
      int rig = min(ri, segtope - 1);
      int solact = s.sol + s.acumulado;
      for (int j = segini; j < lef; j++) {
        solact -= a[j] >= q;
        if (j + m <= n) solact += a[j + m] >= q;
      }
      for (int j = lef; j <= rig; j++) {
        sol = max(sol, solact);
        solact -= a[j] >= q;
        if (j + m <= n) solact += a[j + m] >= q;
      }
    }
  }
  return sol;
}
int anyade[limite];
int acumulado[limite];
int nval = 0;
int valinicial[limite];
vector<segmento> vseg[limite];
vector<accion> vacc[limite];
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  vector<pair<int, int> > w;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    w.push_back(pair<int, int>(a[i], i));
    anyade[max(1, i - (m - 1))]++;
    anyade[i + 1]--;
  }
  sort(w.begin(), w.end());
  int iw = 0;
  while (iw < int(w.size())) {
    if (nval > 0) {
      valinicial[nval] = w[iw].first;
      while (iw < int(w.size()) and w[iw].first == valinicial[nval]) {
        pair<int, int> &p = w[iw];
        int pos = p.second;
        anyade[max(1, pos - (m - 1))]--;
        anyade[pos + 1]++;
        iw++;
      }
    }
    for (int i = 1; i <= n; i++) acumulado[i] = acumulado[i - 1] + anyade[i];
    int iwini = iw;
    iw = min(int(w.size()), iw + base);
    if (iw < int(w.size())) {
      int val = w[iw].first;
      while (w[iw].first == val) iw--;
      iw++;
    }
    map<int, int> pos2pos;
    for (int i = 1; i <= n; i += base) pos2pos[i];
    pos2pos[n + 1];
    for (int i = iwini; i < iw; i++) {
      pair<int, int> &p = w[i];
      int pos = p.second;
      pos2pos[max(1, pos - (m - 1))];
      pos2pos[pos + 1];
    }
    vector<segmento> &vse = vseg[nval];
    vse = vector<segmento>(int(pos2pos.size()));
    {
      int ivse = 0;
      for (map<int, int>::iterator it = pos2pos.begin(); it != pos2pos.end();
           it++, ivse++) {
        vse[ivse].pos = it->first;
        it->second = ivse;
      }
    }
    for (int i = 0; i < int(vse.size()); i++) {
      segmento &s = vse[i];
      int posini = s.pos;
      int postope = n + 1;
      if (i < int(vse.size()) - 1) postope = vse[i + 1].pos;
      s.sol = s.solmax = acumulado[posini];
      for (int pos = posini; pos < postope; pos++)
        s.solmax = max(s.solmax, acumulado[pos]);
    }
    vector<accion> &vac = vacc[nval];
    for (int i = iwini; i < iw; i++) {
      pair<int, int> &p = w[i];
      int val = p.first;
      int pos = p.second;
      vac.push_back(
          accion(val, pos2pos[max(1, pos - (m - 1))], pos2pos[pos + 1]));
      anyade[max(1, pos - (m - 1))]--;
      anyade[pos + 1]++;
    }
    nval++;
  }
  int casos;
  cin >> casos;
  int sol = 0;
  for (int cas = 0; cas < casos; cas++) {
    int le, ri, q;
    cin >> le >> ri >> q;
    q ^= sol;
    int ival = 0;
    while (ival < nval - 1 and valinicial[ival + 1] < q) ival++;
    sol = m - calcula(q, le, ri, vseg[ival], vacc[ival]);
    cout << sol << endl;
  }
}