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;
int n, m, rt[MAXN + 10], Q;
pair<int, int> a[MAXN + 10];
struct Seg_Tree {
  static const int N = 8000000 + 10;
  static const int T = MAXN + 3;
  int ncnt;
  unsigned long long t[N];
  inline 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));
  }
  inline 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);
  }
} seg;
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);
  seg.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 = seg.query(rt[x - 1], 1, n - m + 1, l, r);
    printf("%d\n", ans);
  }
  return 0;
}