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 N = 200010;
unsigned long long a[N * 40 + 150000];
const int b18 = (1 << 18) - 1;
const int b23 = (1 << 23) - 1;
int cnt;
void update(int &first, int second, int l, int r, int L, int R) {
  if (l == r) {
    first = second + 1;
    return;
  }
  first = ++cnt;
  int rc = a[second] & b23;
  int lc = (a[second] >> 23) & b23;
  unsigned long long mx = a[second] >> 46;
  if (l == L && r == R) {
    mx++;
    a[first] = (mx << 46) | ((unsigned long long)lc << 23) | rc;
    return;
  }
  int mid = (l + r) >> 1;
  int lmax, rmax;
  if (l == mid)
    lmax = lc;
  else
    lmax = a[lc] >> 46;
  if (mid + 1 == r)
    rmax = rc;
  else
    rmax = a[rc] >> 46;
  int lazy = mx - max(lmax, rmax);
  if (R <= mid)
    update(lc, lc, l, mid, L, R);
  else if (L > mid)
    update(rc, rc, mid + 1, r, L, R);
  else {
    update(lc, lc, l, mid, L, mid);
    update(rc, rc, mid + 1, r, mid + 1, R);
  }
  if (l == mid)
    lmax = lc;
  else
    lmax = a[lc] >> 46;
  if (mid + 1 == r)
    rmax = rc;
  else
    rmax = a[rc] >> 46;
  mx = max(lmax, rmax);
  mx += lazy;
  a[first] =
      (mx << 46) | ((unsigned long long)lc << 23) | (unsigned long long)rc;
}
int query(int first, int l, int r, int L, int R) {
  if (l == r) {
    return first;
  }
  int rc = a[first] & b23;
  int lc = (a[first] >> 23) & b23;
  int mx = a[first] >> 46;
  if (l == L && R == r) {
    return mx;
  }
  int mid = (l + r) >> 1;
  int lmax, rmax;
  if (l == mid)
    lmax = lc;
  else
    lmax = a[lc] >> 46;
  if (mid + 1 == r)
    rmax = rc;
  else
    rmax = a[rc] >> 46;
  int lazy = mx - max(lmax, rmax);
  if (R <= mid) return lazy + query(lc, l, mid, L, R);
  if (L > mid) return lazy + query(rc, mid + 1, r, L, R);
  return lazy +
         max(query(lc, l, mid, L, mid), query(rc, mid + 1, r, mid + 1, R));
}
pair<int, int> pi[N];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &pi[i].first);
    pi[i].second = i;
  }
  sort(pi + 1, pi + n + 1);
  for (int i = n; i >= 1; i--) {
    int l = max(1, pi[i].second - m + 1);
    int r = min(n - m + 1, pi[i].second);
    update(pi[i].second, pi[i + 1].second, 1, n - m + 1, l, r);
  }
  int q;
  scanf("%d", &q);
  int ans = 0;
  while (q--) {
    int l, r, first;
    scanf("%d%d%d", &l, &r, &first);
    first ^= ans;
    if (first <= pi[1].first) {
      ans = 0;
    } else if (first > pi[n].first) {
      ans = m;
    } else {
      int lt = 1, rt = n, mid, pos;
      while (lt <= rt) {
        mid = (lt + rt) >> 1;
        if (pi[mid].first >= first) {
          pos = mid;
          rt = mid - 1;
        } else
          lt = mid + 1;
      }
      ans = m - query(pi[pos].second, 1, n - m + 1, l, r);
    }
    printf("%d\n", ans);
  }
  return 0;
}