Problem: Inna is fed up with jokes about female logic. So she started using binary logic instead.

Inna has an array of n elements a1[1], a1[2], ..., a1[n]. Girl likes to train in her binary logic, so she does an exercise consisting of n stages: on the first stage Inna writes out all numbers from array a1, on the i-th (i ≥ 2) stage girl writes all elements of array ai, which consists of n - i + 1 integers; the k-th integer of array ai is defined as follows: ai[k] = ai - 1[k] AND ai - 1[k + 1]. Here AND is bit-wise binary logical operation.

Dima decided to check Inna's skill. He asks Inna to change array, perform the exercise and say the sum of all <image> elements she wrote out during the current exercise.

Help Inna to answer the questions!

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 105) — size of array a1 and number of Dima's questions. Next line contains n integers a1[1], a1[2], ..., a1[n] (0 ≤ ai ≤ 105) — initial array elements.

Each of next m lines contains two integers — Dima's question description. Each question consists of two integers pi, vi (1 ≤ pi ≤ n; 0 ≤ vi ≤ 105). For this question Inna should make a1[pi] equals vi, and then perform the exercise. Please, note that changes are saved from question to question.

Output

For each question print Inna's answer on a single line.

Examples

Input

3 4
1 1 1
1 1
2 2
3 2
1 2


Output

6
4
7
12

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long long i, k, m, n, p, v;
long long j;
int a[21][110000];
long long ans[21];
map<int, int> f[21];
map<int, int>::iterator it, ir;
long long two(long long i) { return 1 << (i); }
long long one(long long i) { return i * (i + 1) / 2; }
void init() {
  cin >> n >> m;
  for (i = 1; i <= n; i++) {
    cin >> k;
    j = 0;
    while (k && ++j) {
      a[j][i] = k & 1;
      k = k >> 1;
    }
  }
}
void ins(int i, int x, int y) { f[i].insert(pair<int, int>(x, y)); }
void maintain(long long i, map<int, int>::iterator t) {
  map<int, int>::iterator s;
  s = t;
  s++;
  int l = (*t).first, r = (*t).second, ll = (*s).first, rr = (*s).second;
  if (r == ll - 1) {
    ans[i] = ans[i] - one(r - l + 1) - one(rr - ll + 1) + one(rr - l + 1);
    (*t).second = (*s).second;
    f[i].erase(s);
  }
}
void solve() {
  memset(ans, 0, sizeof(ans));
  for (i = 1; i <= 20; i++) {
    f[i].clear();
    ins(i, -1, -1);
    ins(i, 3 * n, 3 * n);
    j = 1;
    while (j <= n) {
      long long now = j;
      if (!a[i][j])
        j++;
      else {
        while (a[i][j] && j <= n) j++;
        ins(i, now, j - 1);
        ans[i] += one(j - now);
      }
    }
  }
  for (j = 1; j <= m; j++) {
    cin >> p >> v;
    long long out = 0;
    for (i = 1; i <= 20; i++, v = v >> 1) {
      k = v & 1;
      it = f[i].upper_bound(p);
      it--;
      int l = (*it).first, r = (*it).second;
      if (k) {
        if (p > r) {
          ins(i, p, p);
          ans[i]++;
          maintain(i, ++it);
          maintain(i, --it);
        }
      } else {
        if (p >= l && p <= r) {
          f[i].erase(it);
          if (p > l) ins(i, l, p - 1);
          if (r >= p + 1) ins(i, p + 1, r);
          ans[i] = ans[i] - one(r - l + 1) + one(p - l) + one(r - p);
        }
      }
      out += (ans[i] * two(i - 1));
    }
    cout << out << endl;
  }
}
int main() {
  init();
  solve();
  return 0;
}