#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


// Manages linearly independent set in \F_2^n of max weight.
//   S  should be an integral type and support taking a bit and addition (^).
//   T  should support addition and comparison.
//   invariant:  ss[i] = 0  ||  2^i <= ss[i] < 2^(i+1)
template <class S, class T> struct Basis {
  int n;
  vector<S> ss;
  vector<T> ts;
  T total;
  Basis(int n_) : n(n_), ss(n, 0), ts(n, 0), total(0) {}
  void add(S s, T t) {
    total += t;
    for (int i = n; --i >= 0; ) if (s >> i & 1) {
      if (ss[i]) {
        if (ts[i] < t) {
          swap(ss[i], s);
          swap(ts[i], t);
        }
        s ^= ss[i];
      } else {
        ss[i] = s;
        ts[i] = t;
        return;
      }
    }
    total -= t;
  }
};

////////////////////////////////////////////////////////////////////////////////


constexpr int E = 30;
constexpr int D = 20;

// [l, r) is good and dim = d <=> R[d][0][l] <= r < R[d][1][l]
vector<int> R[D][2];
vector<Int> S[D][2];
vector<int> invR[D][2];

void init(int N, int Q, vector<int> A) {
#ifdef LOCAL
cerr<<"[init] "<<N<<" "<<Q<<" "<<A<<endl;
#endif
  for (int d = 0; d < D; ++d) for (int t = 0; t < 2; ++t) {
    R[d][t].assign(N, N + 1);
  }
  
  auto as = A;
  sort(as.begin(), as.end());
  as.erase(unique(as.begin(), as.end()), as.end());
  vector<int> ids(N);
  for (int i = 0; i < N; ++i) ids[i] = lower_bound(as.begin(), as.end(), A[i]) - as.begin();
  
  for (int d = 0; d < D; ++d) {
    // l -> min r s.t. [l, r) contains >= 2^d kinds
    vector<int> freq((int)as.size(), 0);
    int now = 0;
    for (int l = 0, r = 0; l < N; ++l) {
      for (; r < N && now < 1 << d; ++r) if (!freq[ids[r]]++) ++now;
      if (now < 1 << d) break;
      R[d][0][l] = r;
      if (!--freq[ids[l]]) --now;
    }
  }
  
  pair<int, int> basis[E];
  fill(basis, basis + E, make_pair(0, -1));
  int jsLen = 0;
  int js[E];
  fill(js, js + E, N);
  for (int i = N; --i >= 0; ) {
    if (A[i]) {
      pair<int, int> ai(A[i], i);
      for (int e = E; --e >= 0; ) if (ai.first >> e & 1) {
        if (basis[e].first) {
          if (basis[e].second > ai.second) {
            swap(basis[e], ai);
          }
          ai.first ^= basis[e].first;
        } else {
          basis[e] = ai;
          ai = make_pair(0, -1);
          break;
        }
      }
      // insert i
      for (int d = jsLen; --d >= 0; ) js[d + 1] = js[d];
      js[0] = i;
      ++jsLen;
      // erase ai.second
      if (~ai.second) {
        for (int d = 0; d < jsLen; ++d) if (js[d] == ai.second) {
          for (int dd = d + 1; dd < jsLen; ++dd) js[dd - 1] = js[dd];
          js[--jsLen] = N;
          break;
        }
      }
    }
// cerr<<i<<": js = ";pv(js,js+jsLen);
    // js[d - 1] < r <= js[d] ==> dim = d
    for (int d = 0; d < D; ++d) {
      R[d][1][i] = max(R[d][0][i], js[d] + 1);
    }
  }
// for(int d=0;d<5;++d)for(int t=0;t<2;++t)cerr<<"R["<<d<<"]["<<t<<"] = "<<R[d][t]<<endl;
  for (int d = 0; d < D; ++d) for (int t = 0; t < 2; ++t) {
    S[d][t].assign(N + 1, 0);
    for (int i = 0; i < N; ++i) {
      S[d][t][i + 1] = S[d][t][i] + R[d][t][i];
    }
  }
  // lower_bound
  for (int d = 0; d < D; ++d) for (int t = 0; t < 2; ++t) {
    invR[d][t].assign(N + 2, N);
    for (int r = 0, i = 0; i < N; ++i) {
      for (; r <= R[d][t][i]; ++r) invR[d][t][r] = i;
    }
  }
}

Int solve(int l, int r) {
  ++r;
  Int ans = 0;
  for (int d = 0; d < D; ++d) for (int t = 0; t < 2; ++t) {
    int pos = invR[d][t][r + 1];
    chmax(pos, l);
    chmin(pos, r);
    Int sum = 0;
    sum += (S[d][t][pos] - S[d][t][l]);
    sum += (Int)(r - pos) * (r + 1);
    sum -= (Int)(r - l) * l;
    ans += (t ? sum : -sum);
  }
// cerr<<"[solve] "<<l<<" "<<r<<" = "<<ans<<endl;
  return ans;
}