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 std::bitset;
using std::cin;
using std::cout;
using std::endl;
using std::make_pair;
using std::map;
using std::pair;
using std::priority_queue;
using std::queue;
using std::set;
using std::string;
using std::stringstream;
using std::vector;
class MyTimer {
 public:
  void reset() {}
  void report() {}
} myTimer;
template <typename A, typename B>
std::ostream &operator<<(std::ostream &cout, const pair<A, B> &x) {
  return cout << "(" << x.first << ", " << x.second << ")";
}
template <typename T1, typename T2>
inline bool chmin(T1 &a, const T2 &b) {
  return a > b ? a = b, true : false;
}
template <typename T1, typename T2>
inline bool chmax(T1 &a, const T2 &b) {
  return a < b ? a = b, true : false;
}
inline int readint() {
  int a = 0;
  char c = getchar(), p = 0;
  while (isspace(c)) c = getchar();
  if (c == '-') p = 1, c = getchar();
  while (isdigit(c)) a = a * 10 + c - '0', c = getchar();
  return p ? -a : a;
}
const int maxN = 200000 + 233;
const int NODE = maxN * 40 + 60000;
int n, m, q;
unsigned long long data[NODE];
pair<int, int> a[maxN];
int root[maxN];
int cnt = 0;
unsigned long long encode(int x, int y, int z) {
  return (unsigned long long)x << (23 + 18) | (unsigned long long)y << 18 |
         (unsigned long long)z;
}
void decode(unsigned long long code, int &x, int &y, int &z) {
  z = code & ((1 << 18) - 1);
  code >>= 18;
  y = code & ((1 << 23) - 1);
  code >>= 23;
  x = code & ((1 << 23) - 1);
}
int getVal(unsigned long long code) { return code & ((1 << 18) - 1); }
int ql, qr;
void add(int u, int &o, int L, int R) {
  if (L == R) {
    o = u + 1;
    return;
  }
  int lson, rson, val;
  decode(data[u], lson, rson, val);
  int nlson = lson, nrson = rson, nval = val;
  int M = (L + R) >> 1;
  int tag = val - std::min(L == M ? nlson : getVal(data[nlson]),
                           M + 1 == R ? nrson : getVal(data[nrson]));
  o = ++cnt;
  if (ql <= L && R <= qr) {
    ++nval;
  } else {
    if (ql <= M) add(lson, nlson, L, M);
    if (qr > M) add(rson, nrson, M + 1, R);
    nval = std::min(L == M ? nlson : getVal(data[nlson]),
                    M + 1 == R ? nrson : getVal(data[nrson])) +
           tag;
  }
  data[o] = encode(nlson, nrson, nval);
}
int query(int o, int L, int R) {
  if (o == 0) return 0;
  if (L == R) return o;
  int lson, rson, val;
  decode(data[o], lson, rson, val);
  int M = (L + R) >> 1, ans = maxN;
  int tag = val - std::min(L == M ? lson : getVal(data[lson]),
                           M + 1 == R ? rson : getVal(data[rson]));
  if (ql <= L && R <= qr) {
    return val;
  } else {
    if (ql <= M) chmin(ans, query(lson, L, M) + tag);
    if (qr > M) chmin(ans, query(rson, M + 1, R) + tag);
    return ans;
  }
}
int main() {
  fprintf(stderr, "Memory: %.3lf\n", sizeof(data) / 1e6);
  n = readint();
  m = readint();
  for (int i = 1; i <= n; ++i) a[i] = pair<int, int>(readint(), i);
  std::sort(a + 1, a + n + 1);
  root[0] = cnt = 0;
  for (int i = 1; i <= n; ++i) {
    int pos = a[i].second;
    ql = std::max(1, pos - m + 1);
    qr = std::min(pos, n - m + 1);
    add(root[i - 1], root[i], 1, n - m + 1);
    if (NODE - cnt < 50)
      fprintf(stderr, "i = %d, cnt = %d\n", i, cnt), assert(false);
  }
  q = readint();
  int lastans = 0;
  while (q--) {
    ql = readint(), qr = readint();
    int val = readint() ^ lastans;
    int p = std::lower_bound(a + 1, a + n + 1, pair<int, int>(val, 0)) - a;
    --p;
    int rt = root[p];
    printf("%d\n", lastans = query(rt, 1, n - m + 1));
  }
  return 0;
}