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;
set<pair<int, int>, greater<pair<int, int>>> interv[20];
long long add(int bit, int poz);
long long del(int bit, int poz);
int nr[100010];
int main() {
  int n, m;
  cin >> n >> m;
  long long r = 0;
  for (int i = 1; i <= n; i++) cin >> nr[i];
  for (int i = 0; i < 18; i++) {
    int st = 1;
    for (int j = 1; j <= n; j++) {
      if ((nr[j] & (1 << i)) == 0) {
        if (st < j) {
          interv[i].insert({st, j - 1});
          r += 1ll * (1ll << i) * (j - st) * (j - st + 1) / 2ll;
        }
        st = j + 1;
      }
    }
    if (st <= n) {
      interv[i].insert({st, n});
      r += 1ll * (1ll << i) * (n + 1 - st) * (n - st + 2) / 2ll;
    }
  }
  while (m--) {
    int p, val;
    cin >> p >> val;
    for (int i = 0; i < 18; i++) {
      if ((val & (1 << i)) != 0 && (nr[p] & (1 << i)) == 0)
        r += 1ll * (1ll << i) * add(i, p);
      else if ((val & (1 << i)) == 0 && (nr[p] & (1 << i)) != 0)
        r += 1ll * (1ll << i) * del(i, p);
    }
    nr[p] = val;
    cout << r << '\n';
  }
}
long long add(int bit, int poz) {
  pair<int, int> a, b;
  a = {poz, poz};
  long long d = 0;
  if (interv[bit].upper_bound({poz, 1e9}) != interv[bit].end()) {
    a = *interv[bit].upper_bound({poz, 1e9});
    if (a.second == poz - 1) {
      interv[bit].erase(a);
      d -= 1ll * (a.second - a.first + 1) * (a.second - a.first + 2) / 2;
      a.second = poz;
    } else
      a = {poz, poz};
  }
  if (interv[bit].upper_bound({poz + 1, 1e9}) != interv[bit].end()) {
    b = *interv[bit].upper_bound({poz + 1, 1e9});
    if (b.first == poz + 1) {
      interv[bit].erase(b);
      d -= 1ll * (b.second - b.first + 1) * (b.second - b.first + 2) / 2;
      a.second = b.second;
    }
  }
  interv[bit].insert(a);
  d += 1ll * (a.second - a.first + 1) * (a.second - a.first + 2) / 2;
  return d;
}
long long del(int bit, int poz) {
  pair<int, int> c = *interv[bit].upper_bound({poz, 1e9}), a, b;
  interv[bit].erase(c);
  long long d = -1ll * (c.second - c.first + 1) * (c.second - c.first + 2) / 2;
  a = {c.first, poz - 1};
  b = {poz + 1, c.second};
  if (a.first <= a.second) {
    d += 1ll * (a.second - a.first + 1) * (a.second - a.first + 2) / 2;
    interv[bit].insert(a);
  }
  if (b.first <= b.second) {
    d += 1ll * (b.second - b.first + 1) * (b.second - b.first + 2) / 2;
    interv[bit].insert(b);
  }
  return d;
}