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;
void SR(int &x) { scanf("%d", &x); }
void SR(long long &x) { scanf("%lld", &x); }
void SR(double &x) { scanf("%lf", &x); }
void SR(char *s) { scanf("%s", s); }
void RI() {}
template <typename I, typename... T>
void RI(I &x, T &...tail) {
  SR(x);
  RI(tail...);
}
void SP(const int x) { printf("%d", x); }
void SP(const long long x) { printf("%lld", x); }
void SP(const double x) { printf("%.16lf", x); }
void SP(const char *s) { printf(s); }
void PS() { puts(""); }
template <typename I, typename... T>
void PS(I &x, T &...tail) {
  putchar(' ');
  SP(x);
  PS(tail...);
}
void PL() { puts(""); }
template <typename I, typename... T>
void PL(const I x, const T... tail) {
  SP(x);
  PS(tail...);
}
const int TN = 8.06e6;
struct Node {
  static Node mem[TN], *pmem;
  Node() : hi(0), l(0), r(0) {}
  Node(const Node &o) : hi(o.hi), l(o.l), r(o.r) {}
  unsigned long long hi : 18, l : 23, r : 23;
} Node::mem[TN], *Node::pmem = Node::mem;
struct Seg {
  Node *dat = Node::mem;
  Node *&siz = Node::pmem;
  inline int hi(int o, int low, int high) {
    if (low == high) return o;
    return dat[o].hi;
  }
  inline int l(int o) { return dat[o].l; }
  inline int r(int o) { return dat[o].r; }
  int getNode(int x) {
    siz++;
    *siz = Node(dat[x]);
    return siz - dat;
  }
  int tag(int x, int low, int high) {
    int mid = (low + high) / 2;
    return hi(x, low, high) - max(hi(l(x), low, mid), hi(r(x), mid + 1, high));
  }
  void pull(int x, int low, int high, int d) {
    int mid = (low + high) / 2;
    dat[x].hi = max(hi(l(x), low, mid), hi(r(x), mid + 1, high)) + d;
  }
  int add(int x, int low, int high, int a, int b, int k) {
    if (low == high) {
      return x + k;
    }
    int t = getNode(x);
    if (low == a && b == high) {
      dat[t].hi += k;
      return t;
    }
    int mid = (low + high) / 2;
    int d = tag(t, low, high);
    if (b <= mid)
      dat[t].l = add(l(t), low, mid, a, b, k);
    else if (mid + 1 <= a)
      dat[t].r = add(r(t), mid + 1, high, a, b, k);
    else
      dat[t].l = add(l(t), low, mid, a, mid, k),
      dat[t].r = add(r(t), mid + 1, high, mid + 1, b, k);
    pull(t, low, high, d);
    return t;
  }
  int ask(int x, int low, int high, int a, int b) {
    if (low == a && b == high) return hi(x, low, high);
    int t = x;
    int mid = (low + high) / 2;
    int ret = 0;
    if (b <= mid)
      ret = ask(l(t), low, mid, a, b);
    else if (mid + 1 <= a)
      ret = ask(r(t), mid + 1, high, a, b);
    else
      ret = max(ask(l(t), low, mid, a, mid),
                ask(r(t), mid + 1, high, mid + 1, b));
    return ret + tag(t, low, high);
  }
} seg;
const int maxn = 2e5 + 5;
int n, m, a[maxn];
void read() {
  RI(n, m);
  for (int i = (1); i <= int(n); i++) RI(a[i]);
}
int rnk[maxn];
int *t = a;
bool cmp(int x, int y) { return a[x] < a[y]; }
void build() {
  memcpy(rnk, a + 1, sizeof(int) * n);
  sort(rnk, rnk + n);
  for (int i = (1); i <= int(n); i++)
    a[i] = lower_bound(rnk, rnk + n, a[i]) - rnk;
  static int tmp[maxn];
  for (int i = 0; i < int(n); i++) tmp[i] = i + 1;
  sort(tmp, tmp + n, cmp);
  t[n] = 0;
  for (int i = n - 1; i >= 0; i--)
    t[i] = seg.add(t[i + 1], 1, n - m + 1, max(tmp[i] - m + 1, 1),
                   min(tmp[i], n - m + 1), 1);
}
void sol() {
  int s;
  RI(s);
  int ans = 0;
  while (s--) {
    int l, r, x;
    RI(l, r, x);
    int q = x ^ ans;
    int v = lower_bound(rnk, rnk + n, q) - rnk;
    ans = m - seg.ask(t[v], 1, n - m + 1, l, r);
    PL(ans);
  }
}
int main() {
  read();
  build();
  sol();
  return 0;
}