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 = 200050, maxns = 8000050;
int n, m, q, ans;
pair<int, int> a[maxn];
int ts, root[maxn];
unsigned long long tr[maxns];
bool cmp(const int &lhs, const int &rhs) { return a[lhs] < a[rhs]; }
inline void Get(bool lt, bool rt, unsigned long long x, int &ls, int &rs,
                int &s, int &t) {
  s = x % maxn, ls = x / maxn / maxns, rs = x / maxn % maxns;
  t = s - min(lt ? ls : tr[ls] % maxn, rt ? rs : tr[rs] % maxn);
}
inline unsigned long long Chg(int ls, int rs, int s) {
  return ((unsigned long long)ls * maxns + rs) * maxn + s;
}
inline void add(int x0, int &x, int ll, int rr, int li, int ri, int k) {
  if (ll == rr) {
    x = x0 + 1;
    return;
  }
  tr[x = ++ts] = tr[x0];
  if (li <= ll && rr <= ri) {
    tr[x] += k;
    return;
  }
  int mid = (ll + rr) >> 1, lt = (ll == mid), rt = (rr == mid + 1), ls0, rs0,
      s0, ls = 0, rs = 0, s, t;
  Get(lt, rt, tr[x0], ls0, rs0, s0, t);
  if (li <= mid) add(ls0, ls, ll, mid, li, ri, k);
  if (ri > mid) add(rs0, rs, mid + 1, rr, li, ri, k);
  if (!ls) ls = ls0;
  if (!rs) rs = rs0;
  s = min(lt ? ls : tr[ls] % maxn, rt ? rs : tr[rs] % maxn) + t;
  tr[x] = Chg(ls, rs, s);
}
inline int query(int x, int ll, int rr, int li, int ri) {
  if (ll == rr) return x;
  if (!x) return 0;
  if (li <= ll && rr <= ri) return tr[x] % maxn;
  int mid = (ll + rr) >> 1, ls, rs, s, t;
  Get(ll == mid, rr == mid + 1, tr[x], ls, rs, s, t);
  s = maxn;
  if (li <= mid) s = min(s, query(ls, ll, mid, li, ri));
  if (ri > mid) s = min(s, query(rs, mid + 1, rr, li, ri));
  return s + t;
}
int main() {
  int i, j;
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) scanf("%d", &a[i].first), a[i].second = i;
  sort(a + 1, a + 1 + n);
  for (i = 1; i <= n; i++)
    add(root[i - 1], root[i], 1, n - m + 1, a[i].second - m + 1, a[i].second,
        1);
  scanf("%d", &q);
  while (q--) {
    int li, ri, xi, pos;
    scanf("%d%d%d", &li, &ri, &xi);
    xi ^= ans;
    pos = lower_bound(a + 1, a + 1 + n, make_pair(xi, 0)) - a - 1;
    ans = query(root[pos], 1, n - m + 1, li, ri);
    printf("%d\n", ans);
  }
  return 0;
}