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 inf = 1e9;
const long long Inf = 1e18;
const int mod = 1;
template <typename T = int>
T gi() {
  T x = 0, o = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') o = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * o;
}
template <typename T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, 1 : 0;
};
template <typename T>
bool chkmin(T &a, T b) {
  return a > b ? a = b, 1 : 0;
};
int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
void inc(int &a, int b) { a = (a + b >= mod ? a + b - mod : a + b); }
void dec(int &a, int b) { a = (a - b < 0 ? a - b + mod : a - b); }
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + "," + to_string(p.second) + ")";
}
template <typename T>
string to_string(T v) {
  int fst = 1;
  string ret = "{";
  for (auto x : v) {
    if (!fst) ret += ",";
    fst = 0, ret += to_string(x);
  }
  ret += "}";
  return ret;
}
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  dbg_out(T...);
}
template <typename T>
int qpow(int a, T b) {
  int ret = 1;
  while (b) {
    if (b & 1) ret = 1ll * ret * a % mod;
    a = 1ll * a * a % mod, b >>= 1;
  }
  return ret;
}
const int N = 2e5 + 10;
const int M = 450;
int n, m, a[N], bel[N], sz, blo, pre[N], suf[N], val[N], id[N];
int w[N], s[N], sum[N];
struct block {
  int bl, br, tag = 0, f[M], s[M];
  void modify(int l, int r) {
    for (int i = l; i <= r; i++) ++val[i];
  }
  void modify() { ++tag; }
  void pushdown() {
    for (int i = bl; i <= br; i++) val[i] += tag;
    tag = 0;
  }
  void save(int tim) {
    pushdown();
    for (int i = bl; i <= br; i++) chkmax(f[tim], val[i]);
    s[tim] = val[bl];
  }
  int max() {
    int ret = 0;
    for (int i = bl; i <= br; i++) chkmax(ret, val[i]);
    return ret;
  }
  int query(int l, int r, int x, int s) {
    int sum = s, ans = 0;
    for (int i = bl; i < l; i++) sum += (a[i + m] >= x) - (a[i] >= x);
    for (int i = l; i <= r; i++) {
      chkmax(ans, sum);
      sum += (a[i + m] >= x) - (a[i] >= x);
    }
    return ans;
  }
} T[M];
void modify(int l, int r, int k) {
  int L = bel[l], R = bel[r];
  if (L == R)
    T[L].modify(l, r);
  else {
    T[L].modify(l, T[L].br);
    for (int i = L + 1; i < R; i++) T[i].modify();
    T[R].modify(T[R].bl, r);
  }
  pre[k] = T[L].max();
  suf[k] = T[R].max();
}
void save(int tim) {
  for (int i = 1; i <= blo; i++) T[i].save(tim);
}
int query(int l, int r, int x) {
  int L = bel[l], R = bel[r];
  if (L == R)
    return T[L].query(l, r, x, s[L]);
  else {
    int ans = T[L].query(l, T[L].br, x, s[L]);
    for (int i = L + 1; i < R; i++) chkmax(ans, w[i] + sum[i]);
    chkmax(ans, T[R].query(T[R].bl, r, x, s[R]));
    return ans;
  }
}
int main() {
  n = gi(), m = gi();
  for (int i = 1; i <= n; i++) a[i] = gi(), id[i] = i;
  sort(id + 1, id + n + 1, [&](int x, int y) { return a[x] > a[y]; });
  sz = sqrt(n);
  for (int i = 1; i <= n; i++) bel[i] = (i - 1) / sz + 1;
  blo = bel[n];
  for (int i = 1; i <= blo; i++)
    T[i].bl = T[i - 1].br + 1, T[i].br = min(n, i * sz);
  for (int i = 1; i <= n; i++) {
    int x = id[i];
    modify(max(1, x - m + 1), x, i);
    if (bel[i] != bel[i + 1]) save(bel[i]);
  }
  int q = gi(), ans = 0;
  while (q--) {
    int l = gi(), r = gi(), x = gi() ^ ans, t = 1;
    while (t < blo && a[id[T[t].br]] >= x) ++t;
    for (int i = 1; i <= blo; i++)
      w[i] = T[i].f[t - 1], s[i] = T[i].s[t - 1], sum[i] = 0;
    int LL = bel[l], RR = bel[r];
    for (int i = T[t - 1].br + 1; i <= n && a[id[i]] >= x; i++) {
      int x = id[i], l = max(1, x - m + 1), r = x, L = bel[l], R = bel[r];
      if (L == R)
        w[L] = pre[i];
      else {
        w[L] = pre[i];
        ++sum[L + 1], --sum[R];
        w[R] = suf[i];
      }
      if (l <= T[LL].bl && T[LL].bl <= r) ++s[LL];
      if (LL != RR && l <= T[RR].bl && T[RR].bl <= r) ++s[RR];
    }
    for (int i = 1; i <= blo; i++) sum[i] += sum[i - 1];
    ans = m - query(l, r, x);
    printf("%d\n", ans);
  }
  return 0;
}