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;
int a[100005], n, m;
vector<int> v[20];
set<pair<int, int> > myset[20];
set<pair<int, int> >::iterator it;
long long first(int l, int r, int i) {
  long long x = (r - l + 1);
  return (1LL << i) * ((x * (x + 1)) / 2);
}
int main() {
  int i, j;
  scanf("%d", &n);
  scanf("%d", &m);
  for (i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    for (j = 0; j < 18; j++) {
      if (a[i] & (1 << j))
        v[j].push_back(1);
      else
        v[j].push_back(0);
    }
  }
  long long ans = 0;
  for (i = 0; i < 18; i++) {
    int l, r;
    for (j = 0; j < n; j++) {
      while (j < v[i].size() && v[i][j] == 0) j++;
      if (j >= v[i].size()) break;
      l = r = j;
      j++;
      while (j < v[i].size() && v[i][j] == 1) j++;
      j--;
      r = j;
      myset[i].insert({l, r});
      ans += first(l, r, i);
    }
  }
  while (m--) {
    int p, v;
    scanf("%d", &p);
    scanf("%d", &v);
    p--;
    for (i = 0; i < 18; i++) {
      it = myset[i].lower_bound(make_pair(p, 0));
      int l1 = -1000, r1 = -1000, l2 = -1000, r2 = -1000;
      if (it != myset[i].end()) {
        l2 = (*it).first;
        r2 = (*it).second;
      }
      if (it != myset[i].begin()) {
        it--;
        l1 = (*it).first;
        r1 = (*it).second;
      }
      if (v & (1 << i)) {
        if ((p >= l1 && p <= r1) || (p >= l2 && p <= r2)) continue;
        if (r1 + 1 == p && l2 - 1 == p) {
          myset[i].erase(make_pair(l1, r1));
          ans -= first(l1, r1, i);
          myset[i].erase(make_pair(l2, r2));
          ans -= first(l2, r2, i);
          myset[i].insert(make_pair(l1, r2));
          ans += first(l1, r2, i);
        } else if (r1 + 1 == p) {
          myset[i].erase(make_pair(l1, r1));
          ans -= first(l1, r1, i);
          myset[i].insert(make_pair(l1, r1 + 1));
          ans += first(l1, r1 + 1, i);
        } else if (l2 - 1 == p) {
          myset[i].erase(make_pair(l2, r2));
          ans -= first(l2, r2, i);
          myset[i].insert(make_pair(l2 - 1, r2));
          ans += first(l2 - 1, r2, i);
        } else {
          myset[i].insert(make_pair(p, p));
          ans += first(p, p, i);
        }
      } else {
        if (p >= l1 && p <= r1) {
          myset[i].erase(make_pair(l1, r1));
          ans -= first(l1, r1, i);
          int x1 = l1, y1 = p - 1, x2 = p + 1, y2 = r1;
          if (x1 <= y1) {
            myset[i].insert(make_pair(x1, y1));
            ans += first(x1, y1, i);
          }
          if (x2 <= y2) {
            myset[i].insert(make_pair(x2, y2));
            ans += first(x2, y2, i);
          }
        } else if (p >= l2 && p <= r2) {
          myset[i].erase(make_pair(l2, r2));
          ans -= first(l2, r2, i);
          int x1 = l2, y1 = p - 1, x2 = p + 1, y2 = r2;
          if (x1 <= y1) {
            myset[i].insert(make_pair(x1, y1));
            ans += first(x1, y1, i);
          }
          if (x2 <= y2) {
            myset[i].insert(make_pair(x2, y2));
            ans += first(x2, y2, i);
          }
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}