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>
const int N = 2e5 + 100;
const int SQRT = 512;
int getBlock(int idx) { return idx / SQRT; }
int getTop(int l) { return ((l + SQRT - 1) / SQRT) * SQRT; }
int n, m;
std::vector<int> a;
void read() {
  scanf("%d%d", &n, &m);
  a.resize(n);
  for (int& x : a) scanf("%d", &x);
}
struct T2 {
  int val;
  int new_sum;
  int new_max;
};
struct BlockBase {
  int task1_sum;
  int task2_sum;
  int task2_max;
};
struct Block {
  BlockBase base;
  std::vector<int> task1_changes;
  std::vector<T2> task2;
  BlockBase get(int val) const {
    auto res = base;
    for (auto x1 : task1_changes) {
      if (x1 <= val) break;
      res.task1_sum++;
    }
    for (auto x1 : task2) {
      {};
      {};
      if (x1.val <= val) break;
      {};
      {};
      {};
      {};
      res.task2_sum = x1.new_sum;
      res.task2_max = x1.new_max;
    }
    return res;
  }
};
Block d[SQRT][SQRT];
using Pair = std::pair<int, int>;
std::vector<int> times;
std::vector<Pair> tidxs;
void task1_prep() {
  for (int i = 0; i < n; ++i) {
    Pair p = tidxs[i];
    if (i != 0 && getBlock(i - 1) != getBlock(i)) {
      int tb = getBlock(i);
      for (int j = 0; j < SQRT; ++j) d[j][tb].base = d[j][tb - 1].get(p.first);
    }
    int idx = p.second;
    int pos = getBlock(idx);
    int tb = getBlock(i);
    d[pos][tb].task1_changes.push_back(p.first);
  }
}
int curState[N] = {};
T2 stupidGetBlock(int pos) {
  T2 r;
  r.new_max = 0;
  int res = 0;
  for (int i = pos * SQRT; i < (pos + 1) * SQRT; ++i) {
    res += curState[i];
    {};
    {};
    r.new_max = std::max(r.new_max, res);
  }
  r.new_sum = res;
  return r;
}
void task2_prep() {
  for (int i = 0; i < n; ++i) {
    Pair p = tidxs[i];
    if (i != 0 && getBlock(i - 1) != getBlock(i)) {
      {};
      int tb = getBlock(i);
      for (int j = 0; j < SQRT; ++j) {
        d[j][tb].base = d[j][tb - 1].get(p.first - 1);
        if (j == 2) {
          {};
          {};
        }
      }
    }
    int idx = p.second;
    int pos = getBlock(idx);
    int tb = getBlock(i);
    {
      curState[idx]--;
      T2 x = stupidGetBlock(pos);
      x.val = p.first;
      d[pos][tb].task2.push_back(x);
      if (idx == 10) {
        {};
        {};
      }
    }
    if (idx - m >= 0) {
      curState[idx - m]++;
      int pp = getBlock(idx - m);
      T2 x = stupidGetBlock(pp);
      x.val = p.first;
      d[pp][tb].task2.push_back(x);
    }
  }
}
void prep() {
  times = a;
  std::sort(times.rbegin(), times.rend());
  for (int i = 0; i < n; ++i) tidxs.push_back(Pair(a[i], i));
  std::sort(tidxs.rbegin(), tidxs.rend());
  task1_prep();
  task2_prep();
}
int f(int v) {
  if (times[0] <= v) return 0;
  int j = 0;
  for (int i = 0; i < n; i += SQRT, ++j)
    if (times[i] <= v) break;
  return j - 1;
}
int task1_get(int l, int r, int v, int fv) {
  int res = 0;
  int L = getBlock(l);
  int R = getBlock(r);
  if (L == R) {
    for (int i = l; i <= r; ++i) res += (a[i] > v);
    return res;
  }
  for (int i = l; i < (L + 1) * SQRT; ++i) res += (a[i] > v);
  for (int i = R * SQRT; i <= r; ++i) res += (a[i] > v);
  for (int b = L + 1; b < R; ++b) res += d[b][fv].get(v).task1_sum;
  return res;
}
void shift1(int pos, int v, int& res, int& cur) {
  if (a[pos] > v) --cur;
  if (a[pos + m] > v) ++cur;
  res = std::max(res, cur);
}
void shift2(int pos, int v, int fv, int& res, int& cur) {
  {};
  int cc = cur;
  auto r = d[pos][fv].get(v);
  {};
  {};
  cur += r.task2_sum;
  cc += r.task2_max;
  res = std::max(res, cc);
  res = std::max(res, cur);
}
int task2_get(int l, int r, int v) {
  int res;
  int fv = f(v);
  int cur = task1_get(l, l + m - 1, v, fv);
  {};
  {};
  res = cur;
  int L = getBlock(l);
  int R = getBlock(r);
  if (L == R) {
    for (int i = l; i < r; ++i) shift1(i, v, res, cur);
    return res;
  }
  {};
  for (int i = l; i < (L + 1) * SQRT; ++i) shift1(i, v, res, cur);
  {};
  {};
  {};
  for (int b = L + 1; b < R; ++b) {
    shift2(b, v, fv, res, cur);
    {};
    {};
    {};
  }
  {};
  for (int i = R * SQRT; i < r; ++i) shift1(i, v, res, cur);
  {};
  return res;
}
int main() {
  read();
  prep();
  int s;
  scanf("%d", &s);
  int ans = 0;
  for (int i = 0; i < s; ++i) {
    int l, r, x;
    scanf("%d%d%d", &l, &r, &x);
    --l;
    --r;
    int q = x ^ ans;
    int gg = task2_get(l, r, q - 1);
    ans = m - gg;
    printf("%d\n", ans);
  }
}