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 = 200000;
const int N = 8000000 + 10;
const int T = MAXN + 3;
int n, m, rt[MAXN + 10], Q;
pair<int, int> a[MAXN + 10];
int ncnt;
unsigned long long t[N];
void calc_s(const bool &nl, const bool &nr, unsigned long long x, int &ls,
            int &rs, int &tag) {
  int s = x % T;
  ls = x / T / N;
  rs = x / T % N;
  tag = s - min((nl ? ls : t[ls] % T), (nr ? rs : t[rs] % T));
}
unsigned long long calc(const int &ls, const int &rs, const int &val) {
  return (1ull * ls * N + rs) * T + val;
}
void ins(const int &last, int &u, const int &L, const int &R, const int &l,
         const int &r) {
  if (L == R) {
    u = last + 1;
    return;
  }
  t[u = ++ncnt] = t[last];
  if (l <= L && R <= r) {
    t[u]++;
    return;
  }
  int mid = (L + R) >> 1, ls, rs, val, lson = 0, rson = 0;
  calc_s((L == mid), (R == mid + 1), t[u], ls, rs, val);
  if (l <= mid) ins(ls, lson, L, mid, l, r);
  if (r > mid) ins(rs, rson, mid + 1, R, l, r);
  if (!lson) lson = ls;
  if (!rson) rson = rs;
  val += min(((L == mid) ? lson : t[lson] % T),
             ((R == mid + 1) ? rson : t[rson] % T));
  t[u] = calc(lson, rson, val);
}
int query(const int &u, const int &L, const int &R, const int &l,
          const int &r) {
  if (L == R) return u;
  if (!u) return 0;
  if (l <= L && R <= r) return t[u] % T;
  int mid = (L + R) >> 1, ls, rs, val, ret = N;
  calc_s((L == mid), (mid + 1 == R), t[u], ls, rs, val);
  if (l <= mid) ret = min(ret, query(ls, L, mid, l, r));
  if (r > mid) ret = min(ret, query(rs, mid + 1, R, l, r));
  return ret + val;
}
inline void build() {
  for (int i = 1; i <= n; i++)
    ins(rt[i - 1], rt[i], 1, n - m + 1, max(1, a[i].second - m + 1),
        a[i].second);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i].first), a[i].second = i;
  sort(a + 1, a + 1 + n);
  build();
  scanf("%d", &Q);
  int ans = 0;
  for (int i = 1; i <= Q; i++) {
    int x, l, r;
    scanf("%d%d%d", &l, &r, &x);
    x ^= ans;
    x = lower_bound(a + 1, a + 1 + n, make_pair(x, 0)) - a;
    if (x == 1)
      ans = 0;
    else
      ans = query(rt[x - 1], 1, n - m + 1, l, r);
    printf("%d\n", ans);
  }
  return 0;
}