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 N = 2e5 + 3, T = 8e6;
int n, m, Q, ans, pool, ql, qr, qx, ts, rt[N];
pair<int, int> a[N];
unsigned long long tr[T];
inline bool cmp(const int &x, const int &y) { return a[x] < a[y]; }
inline void calc_son(const bool &nL, const bool &nR, unsigned long long x,
                     int &ls, int &rs, int &val) {
  ts = x % N;
  ls = x / N / T;
  rs = x / N % T;
  val = ts - min(nL ? ls : tr[ls] % N, nR ? rs : tr[rs] % N);
}
inline unsigned long long calc_t(const int &ls, const int &rs, const int &val) {
  return ((unsigned long long)ls * T + rs) * N + val;
}
inline void add(const int &dup, int &k, const int &l, const int &r,
                const int &x, const int &y) {
  if (l == r) {
    k = dup + 1;
    return;
  }
  tr[k = ++pool] = tr[dup];
  if (l >= x && r <= y) {
    ++tr[k];
    return;
  }
  int mid = l + r >> 1, ls, rs, L = 0, R = 0, val;
  calc_son((l == mid), (mid + 1 == r), tr[dup], ls, rs, val);
  if (x <= mid) add(ls, L, l, mid, x, y);
  if (y > mid) add(rs, R, mid + 1, r, x, y);
  if (!L) L = ls;
  if (!R) R = rs;
  val += min((l == mid) ? L : tr[L] % N, (mid + 1 == r) ? R : tr[R] % N);
  tr[k] = calc_t(L, R, val);
}
inline void build_tree() {
  for (int i = (1); i <= (n); ++i)
    add(rt[i - 1], rt[i], 1, n - m + 1, max(1, a[i].second - m + 1),
        a[i].second);
}
inline int Query(const int &k, const int &l, const int &r, const int &x,
                 const int &y) {
  if (l == r) return k;
  if (!k) return 0;
  if (l >= x && r <= y) return tr[k] % N;
  int mid = l + r >> 1, L, R, val, smin = N;
  calc_son((l == mid), (mid + 1 == r), tr[k], L, R, val);
  if (x <= mid) smin = min(smin, Query(L, l, mid, x, y));
  if (y > mid) smin = min(smin, Query(R, mid + 1, r, x, y));
  return smin + val;
}
char ch;
int Rres;
inline int read() {
  while (ch = getchar(), ch < '0' || ch > '9')
    ;
  Rres = ch - 48;
  while (ch = getchar(), ch >= '0' && ch <= '9') Rres = Rres * 10 + ch - 48;
  return Rres;
}
int main() {
  n = read();
  m = read();
  for (int i = (1); i <= (n); ++i) a[i].first = read(), a[i].second = i;
  sort(a + 1, a + n + 1);
  build_tree();
  Q = read();
  while (Q--) {
    ql = read(), qr = read(), qx = read();
    qx ^= ans;
    qx = lower_bound(a + 1, a + n + 1, make_pair(qx, 0)) - a - 1;
    if (qx == 0) {
      printf("%d\n", ans = 0);
      continue;
    }
    printf("%d\n", ans = Query(rt[qx], 1, n - m + 1, ql, qr));
  }
  return 0;
}