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;
template <typename T>
inline bool chkmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
const int oo = 0x3f3f3f3f;
const int maxn = 200000, max0 = 300, max1 = 700, max2 = 700, maxabs = 1 << 30;
int n, m;
vector<int> X;
int a[maxn + 5];
vector<int> id[max1 + 5], Min[max1 + 5], cnt[max1 + 5], to_add[max1 + 5];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = (0), _end_ = (n); i < _end_; ++i)
    scanf("%d", a + i), X.push_back(a[i]);
  X.push_back(maxabs);
  sort((X).begin(), (X).end());
  X.resize(unique((X).begin(), (X).end()) - X.begin());
  int tot = 0;
  for (int i = (0), _end_ = ((int((X).size()))); i < _end_; ++i) {
    if (!(i % max0)) {
      static int sum[maxn + 5];
      static bool imp[maxn + 5];
      memset(sum, 0, sizeof sum);
      memset(imp, 0, sizeof imp);
      for (int j = (0), _end_ = (n); j < _end_; ++j) {
        if (!(j % max2)) imp[j] = 1;
        if (a[j] < X[i]) {
          --sum[j + 1];
          ++sum[max(0, j - m + 1)];
        } else if (a[j] >= X[i] &&
                   a[j] < X[min((int((X).size())) - 1, i + max0)]) {
          to_add[tot].push_back(j);
          imp[j + 1] = 1;
          imp[max(0, j - m + 1)] = 1;
        }
      }
      int now = -1, pre = 0;
      for (int j = (0), _end_ = (n); j < _end_; ++j) {
        pre += sum[j];
        if (imp[j]) {
          ++now;
          id[tot].push_back(j);
          Min[tot].push_back(pre);
          cnt[tot].push_back(pre);
        }
        chkmin(Min[tot][now], pre);
      }
      id[tot].push_back(n);
      ++tot;
    }
  }
  int qn, lastans = 0;
  scanf("%d", &qn);
  static int lst[maxn + 5], sum[maxn + 5];
  memset(lst, -1, sizeof lst);
  for (int i = (0), _end_ = (qn); i < _end_; ++i) {
    int l, r, z;
    scanf("%d%d%d", &l, &r, &z), --l;
    z ^= lastans;
    int tmp = lower_bound((X).begin(), (X).end(), z) - X.begin();
    int p = tmp / max0;
    for (auto first : to_add[p])
      if (a[first] < z) {
        if (lst[first + 1] != i) sum[first + 1] = 0, lst[first + 1] = i;
        --sum[first + 1];
        if (lst[max(0, first + 1 - m)] != i)
          sum[max(0, first + 1 - m)] = 0, lst[max(0, first + 1 - m)] = i;
        ++sum[max(0, first + 1 - m)];
      }
    int pre = 0;
    int ans = oo;
    for (int j = (0), _end_ = ((int((id[p]).size())) - 1); j < _end_; ++j) {
      int u = id[p][j], v = id[p][j + 1];
      if (lst[id[p][j]] == i) pre += sum[id[p][j]];
      if (u >= l && v < r)
        chkmin(ans, pre + Min[p][j]);
      else {
        if (v <= l || u >= r) continue;
        int now = cnt[p][j] + pre;
        for (int k = (u), _end_ = (v); k < _end_; ++k) {
          if (k >= l && k < r) chkmin(ans, now);
          if (a[k] < X[p * max0]) --now;
          if (k + m < n && a[k + m] < X[p * max0]) ++now;
        }
      }
    }
    printf("%d\n", ans);
    lastans = ans;
  }
  return 0;
}