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 inf = 1e9 + 333;
const long long linf = 1e18 + 333;
const int N = 2e5 + 5;
const int SIZE = 8000000;
class tree {
 public:
  unsigned long long min : 18, l : 23, r : 23;
  tree() { min = l = r = 0; }
};
int n, m, q, cnt, x1, x2, t[N];
pair<int, int> a[N];
tree p[SIZE];
int insert(int t, int l, int r) {
  if (l == r) return t + 1;
  int x = ++cnt;
  if (x1 <= l and r <= x2) {
    p[x] = p[t];
    p[x].min++;
    return x;
  }
  int m = l + r >> 1;
  p[x] = p[t];
  int add = p[x].min - min((l == m ? p[x].l : p[p[x].l].min),
                           (m + 1 == r ? p[x].r : p[p[x].r].min));
  if (x1 <= m) p[x].l = insert(p[t].l, l, m);
  if (x2 > m) p[x].r = insert(p[t].r, m + 1, r);
  p[x].min = min((l == m ? p[x].l : p[p[x].l].min),
                 (m + 1 == r ? p[x].r : p[p[x].r].min)) +
             add;
  return x;
}
int query(int x, int l, int r) {
  if (x2 < l or r < x1) return inf;
  if (l == r) return x;
  if (x1 <= l and r <= x2) return p[x].min;
  int m = l + r >> 1;
  int add = p[x].min - min((l == m ? p[x].l : p[p[x].l].min),
                           (m + 1 == r ? p[x].r : p[p[x].r].min));
  return min(query(p[x].l, l, m), query(p[x].r, m + 1, r)) + add;
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i].first);
    a[i].second = i;
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; i++) {
    x1 = max(1, a[i].second - m + 1);
    x2 = min(a[i].second, n - m + 1);
    t[i] = insert(t[i - 1], 1, n - m + 1);
  }
  scanf("%d", &q);
  int ans = 0;
  for (int qq = 0; qq < q; qq++) {
    int x;
    scanf("%d %d %d", &x1, &x2, &x);
    x = lower_bound(a + 1, a + n + 1, pair<int, int>(x ^ ans, 0)) - a - 1;
    ans = query(t[x], 1, n - m + 1);
    printf("%d\n", ans);
  }
  return 0;
}