#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 2e5;
const int Q = 1e6;
const int LG = 18;
const int W = 9;

int n, q, v;
int a[N + 5], pos[N + 5], block;
struct Query {
  int l, r, id;
  bool operator<(const Query &o) const {
    return pos[l] != pos[o.l] ? pos[l] < pos[o.l] : pos[l] & 1 ? r < o.r : r > o.r;
  }
} qry[Q + 5];

struct SqrtDecomposition {
  int add[1 << W], val[1 << LG];
  void clear() { memset(add, 0, sizeof add), memset(val, 0, sizeof val); }
  int query(int x) { return add[x >> W] + val[x]; }
  void insert(int x) {
    for (int k = LG - 1; k >= W; --k) 
      if (v >> k & 1) {
        int l = (x ^ v ^ (1 << k)) & ~((1 << k) - 1);
        int r = l + (1 << k) - 1;
        for (int i = l >> W; i < (r + 1) >> W; ++i) ++add[i];
      }
    for (int k = W - 1; k >= 0; --k) 
      if (v >> k & 1) {
        int l = (x ^ v ^ (1 << k)) & ~((1 << k) - 1);
        int r = l + (1 << k) - 1;
        for (int i = l; i <= r; ++i) ++val[i];
      }
  }
} sd;

int f[N + 5];
vector<tuple<int, int, int, int>> upd[N + 5];
ll ans[Q + 5];

int main() {
  scanf("%d%d", &n, &v), ++v;
  for (int i = 1; i <= n; ++i)
    scanf("%d", a + i), f[i] = sd.query(a[i]), sd.insert(a[i]), printf("%d%c", f[i], " \n"[i == n]);
  scanf("%d", &q), block = ceil(n / sqrt(q));
  for (int i = 1; i <= n; ++i) pos[i] = (i - 1) / block + 1;
  for (int i = 1; i <= q; ++i) scanf("%d%d", &qry[i].l, &qry[i].r), qry[i].id = i;
  sort(qry + 1, qry + q + 1);
  for (int i = 1, l = 1, r = 0; i <= q; ++i) {
    if (r < qry[i].r) upd[l - 1].emplace_back(r + 1, qry[i].r, -1, qry[i].id);
    while (r < qry[i].r) ans[qry[i].id] += f[++r];
    if (l > qry[i].l) upd[r].emplace_back(qry[i].l, l - 1, 1, qry[i].id);
    while (l > qry[i].l) ans[qry[i].id] -= f[--l] + 1;
    if (r > qry[i].r) upd[l - 1].emplace_back(qry[i].r + 1, r, 1, qry[i].id);
    while (r > qry[i].r) ans[qry[i].id] -= f[r--];
    if (l < qry[i].l) upd[r].emplace_back(l, qry[i].l - 1, -1, qry[i].id);
    while (l < qry[i].l) ans[qry[i].id] += f[l++] + 1;
  }
  sd.clear();
  for (int i = 1; i <= n; ++i) {
    sd.insert(a[i]);
    for (auto [l, r, w, id] : upd[i])
      for (int j = l; j <= r; ++j) ans[id] += sd.query(a[j]) * w;
  }
  for (int i = 1; i <= q; ++i) ans[qry[i].id] += ans[qry[i - 1].id];
  for (int i = 1; i <= q; ++i) printf("%lld\n", ans[i]);
}