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 M = 500, MAXN = 2e5 + 5;
int n, s, val[MAXN], m;
pair<int, int> sum[M][2 * M], pref[M][2 * M], func[MAXN][4];
pair<int, int> svals[MAXN];
int npfunc[MAXN], npsum[M];
int firstm[MAXN];
int lsum[M], lpref[M], lfunc[MAXN];
int bs[M][M];
void comppref(int x, int i) {
  int best = 0;
  int sum1 = 0;
  for (int j = x * M; j < min(x * M + M, n); ++j)
    sum1 += npfunc[j], best = min(best, sum1);
  if (lpref[x] > 0 && pref[x][lpref[x] - 1].first == i + 1) lpref[x]--;
  pref[x][lpref[x]] = pair<int, int>(i + 1, best);
  lpref[x]++;
}
void build() {
  for (int i = 0; i < n; ++i) {
    int x = svals[i].second;
    if (x + m < n) {
      npfunc[x]--;
      func[x][lfunc[x]] = (pair<int, int>(i + 1, npfunc[x]));
      lfunc[x]++;
      npsum[x / M]--;
      sum[x / M][lsum[x / M]] = (pair<int, int>(i + 1, npsum[x / M]));
      lsum[x / M]++;
      comppref(x / M, i);
    }
    if (x - m >= 0) {
      npfunc[x - m]++;
      if (lfunc[x - m] > 0 && func[x - m][lfunc[x - m] - 1].first == i + 1)
        lfunc[x - m]--;
      func[x - m][lfunc[x - m]] = (pair<int, int>(i + 1, npfunc[x - m]));
      lfunc[x - m]++;
      if (lsum[(x - m) / M] > 0 &&
          sum[(x - m) / M][lsum[(x - m) / M] - 1].first == i + 1)
        lsum[(x - m) / M]--;
      npsum[(x - m) / M]++;
      sum[(x - m) / M][lsum[(x - m) / M]] =
          (pair<int, int>(i + 1, npsum[(x - m) / M]));
      lsum[(x - m) / M]++;
      comppref((x - m) / M, i);
    }
  }
}
void buildbs() {
  for (int i = 0; i < M; ++i)
    for (int j = 0; j < M; ++j) bs[i][j] = -1;
  for (int i = 0; i < (n + M - 1) / M; ++i) {
    int ptr = -1;
    for (int j = 0; j < M; ++j) {
      while (ptr < lsum[i] - 1 && sum[i][ptr + 1].first <= j * M) ptr++;
      bs[i][j] = ptr;
    }
  }
}
int ask(int type, int q, int x) {
  if (type == 1) {
    int lo = -1, hi = lfunc[x] - 1;
    while (lo != hi) {
      int mid = (lo + hi + 1) / 2;
      if (func[x][mid].first > q)
        hi = mid - 1;
      else
        lo = mid;
    }
    if (lo == -1) return 0;
    return func[x][lo].second;
  }
  if (type == 2) {
    int lo = bs[x][q / M], hi = min(bs[x][q / M + 1] + 1, lsum[x] - 1);
    while (lo != hi) {
      int mid = (lo + hi + 1) / 2;
      if (sum[x][mid].first > q)
        hi = mid - 1;
      else
        lo = mid;
    }
    if (lo == -1) return 0;
    return sum[x][lo].second;
  }
  if (type == 3) {
    int lo = bs[x][q / M], hi = min(bs[x][q / M + 1] + 1, lpref[x] - 1);
    while (lo != hi) {
      int mid = (lo + hi + 1) / 2;
      if (pref[x][mid].first > q)
        hi = mid - 1;
      else
        lo = mid;
    }
    if (lo == -1) return 0;
    return pref[x][lo].second;
  }
}
int prefix(int l, int q) {
  int sum1 = 0;
  int l1 = l / M;
  for (int i = 0; i < l1; ++i) sum1 += ask(2, q, i);
  for (int i = l1 * M; i < l; ++i) sum1 += ask(1, q, i);
  return sum1 + firstm[q];
}
int query(int l, int r, int q) {
  int best = 0, sum1 = 0, s = 0;
  int l1 = l / M, r1 = r / M;
  if (l1 == r1) {
    for (int i = l; i < r; ++i) {
      sum1 += ask(1, q, i);
      best = min(best, sum1);
    }
  } else {
    for (int i = l; i < l1 * M + M; ++i)
      sum1 += ask(1, q, i), best = min(best, sum1);
    for (int i = l1 + 1; i < r1; ++i) {
      s = sum1 + ask(3, q, i);
      best = min(best, s), sum1 += ask(2, q, i);
    }
    for (int i = r1 * M; i < r; ++i)
      sum1 += ask(1, q, i), best = min(best, sum1);
  }
  return best + prefix(l, q);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    scanf("%d", val + i);
    svals[i] = pair<int, int>(val[i], i);
  }
  sort(svals, svals + n);
  for (int i = 0; i < n; ++i) {
    val[svals[i].second] = i + 1;
    if (svals[i].second < m)
      firstm[i + 1] = firstm[i] + 1;
    else
      firstm[i + 1] = firstm[i];
  }
  build();
  buildbs();
  for (int i = 0; i < M; ++i) assert(lsum[i] == lpref[i]);
  scanf("%d", &s);
  long long ans = 0;
  for (int i = 0; i < s; ++i) {
    int l, r, x;
    scanf("%d%d%d", &l, &r, &x);
    x ^= ans;
    x--;
    l--;
    r--;
    if (x == -1) {
      ans = 0;
      printf("%d\n", ans);
      continue;
    }
    int lo = -1, hi = n - 1;
    while (lo != hi) {
      int mid = (lo + hi + 1) / 2;
      if (svals[mid].first > x)
        hi = mid - 1;
      else
        lo = mid;
    }
    x = lo + 1;
    if (x == 0) {
      ans = 0;
      printf("%d\n", ans);
      continue;
    }
    ans = query(l, r, x);
    printf("%d\n", ans);
  }
}