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 = (int)2e5 + 5, SIZE = 500;
int n, m, size, bnum;
int a[N], ord[N];
bool cmpa(const int i, const int j) { return a[i] > a[j]; }
int val[N], ma[SIZE], delta[SIZE], first[SIZE];
int tma[SIZE][SIZE], tdelta[SIZE][SIZE], tfirst[SIZE][SIZE];
int ttma[N][2];
int main() {
  scanf("%d%d", &n, &m);
  for (size = 0; size * size < n; size++)
    ;
  bnum = n / size + 1;
  for (int i = 0; i < n; i++) scanf("%d", &a[i]), ord[i] = i;
  sort(ord, ord + n, cmpa);
  for (int i = 0; i < n; i++) {
    if (i % size == 0) {
      int tb = i / size;
      for (int j = 0; j < bnum; j++) {
        tma[tb][j] = ma[j];
        tdelta[tb][j] = delta[j];
        tfirst[tb][j] = val[j * size] + delta[j];
      }
    }
    int l = max(0, ord[i] - (m - 1)), r = ord[i] + 1;
    int bl = l / size, br = r / size;
    if (bl == br) {
      for (int j = l; j < r; j++) {
        ++val[j];
        ma[bl] = max(ma[bl], val[j]);
      }
    } else {
      for (int j = l; j < (bl + 1) * size; j++) {
        ++val[j];
        ma[bl] = max(ma[bl], val[j]);
      }
      for (int j = bl + 1; j < br; j++) {
        delta[j]++;
      }
      for (int j = br * size; j < r; j++) {
        ++val[j];
        ma[br] = max(ma[br], val[j]);
      }
    }
    ttma[i][0] = ma[bl];
    ttma[i][1] = ma[br];
  }
  if (n % size == 0) {
    int tb = n / size;
    for (int j = 0; j < bnum; j++) {
      tma[tb][j] = ma[j];
      tdelta[tb][j] = delta[j];
      tfirst[tb][j] = val[j * size] + delta[j];
    }
  }
  int q;
  scanf("%d", &q);
  int ans = 0;
  while (q--) {
    int l, r, x;
    scanf("%d%d%d", &l, &r, &x);
    l--;
    x ^= ans;
    ans = 0;
    a[n] = x;
    int tim = upper_bound(ord, ord + n, n, cmpa) - ord;
    int tb = tim / size;
    for (int j = 0; j < bnum; j++) {
      delta[j] = 0;
      ma[j] = tma[tb][j];
      first[j] = tfirst[tb][j];
    }
    for (int i = tb * size; i < tim; i++) {
      int l = max(0, ord[i] - (m - 1)), r = ord[i] + 1;
      int bl = l / size, br = r / size;
      if (bl < br) {
        delta[bl + 1]++;
        delta[br]--;
      }
      if (l % size == 0) first[bl]++;
      if (r % size && bl != br) first[br]++;
      ma[bl] = ttma[i][0];
      ma[br] = ttma[i][1];
    }
    for (int j = 0; j < bnum; j++) delta[j + 1] += delta[j];
    for (int j = 0; j < bnum; j++)
      first[j] += delta[j], delta[j] += tdelta[tb][j];
    int bl = l / size, br = r / size;
    for (int j = bl + 1; j < br; j++) {
      ans = max(ans, ma[j] + delta[j]);
    }
    {
      int v = first[bl];
      for (int j = bl * size; j < (bl + 1) * size; j++) {
        if (j >= l && j < r) ans = max(ans, v);
        if (a[j] >= x) v--;
        if (j + m < n && a[j + m] >= x) v++;
      }
    }
    {
      int v = first[br];
      for (int j = br * size; j < r; j++) {
        if (j >= l && j < r) ans = max(ans, v);
        if (a[j] >= x) v--;
        if (j + m < n && a[j + m] >= x) v++;
      }
    }
    printf("%d\n", ans = m - ans);
  }
}