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>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
using namespace std;
const double PI = acos(-1.0);
const long long N = 1e5 + 10;
const long long M = 21;
set<pair<long long, long long>> se[M];
long long ar[N];
long long n, m;
long long ans = 0;
long long c2(long long n) { return (n * (n + 1)) / 2; }
void add(long long p, long long bit) {
  auto pr = se[bit].lower_bound({p, -1});
  auto pl = --pr;
  ++pr;
  pair<long long, long long> tmpl = *pl;
  pair<long long, long long> tmpr = *pr;
  if (tmpl.second == p - 1 && tmpr.first == p + 1) {
    ans -= c2(tmpl.second - tmpl.first + 1) + c2(tmpr.second - tmpr.first + 1);
    ans += c2(tmpr.second - tmpl.first + 1);
    se[bit].erase(pl);
    se[bit].erase(pr);
    se[bit].insert({tmpl.first, tmpr.second});
  } else if (tmpl.second == p - 1) {
    ans -= c2(tmpl.second - tmpl.first + 1);
    ans += c2(p - tmpl.first + 1);
    se[bit].erase(pl);
    se[bit].insert({tmpl.first, p});
  } else if (tmpr.first == p + 1) {
    ans -= c2(tmpr.second - tmpr.first + 1);
    ans += c2(tmpr.second - p + 1);
    se[bit].erase(pr);
    se[bit].insert({p, tmpr.second});
  } else {
    ans += 1;
    se[bit].insert({p, p});
  }
}
void sub(long long p, long long bit) {
  auto pt = se[bit].upper_bound({p, 1e7});
  pt--;
  auto tmp = *pt;
  assert(tmp.first <= p && tmp.second >= p);
  if (tmp.first == tmp.second) {
    ans -= c2(1);
    se[bit].erase(pt);
  } else if (tmp.first == p) {
    ans -= c2(tmp.second - tmp.first + 1);
    ans += c2(tmp.second - tmp.first);
    se[bit].erase(pt);
    se[bit].insert({tmp.first + 1, tmp.second});
  } else if (tmp.second == p) {
    ans -= c2(tmp.second - tmp.first + 1);
    ans += c2(tmp.second - tmp.first);
    se[bit].erase(pt);
    se[bit].insert({tmp.first, tmp.second - 1});
  } else {
    ans -= c2(tmp.second - tmp.first + 1);
    ans += c2(p - tmp.first);
    ans += c2(tmp.second - p);
    se[bit].erase(pt);
    se[bit].insert({tmp.first, p - 1});
    se[bit].insert({p + 1, tmp.second});
  }
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (long long i = 1; i <= n; i++) {
    cin >> ar[i];
  }
  for (long long i = 0; i < M; i++) {
    se[i].insert({-1, -1});
    se[i].insert({1e6, 1e6});
    long long cur = 0;
    for (long long j = 1; j <= n; j++) {
      if (!((1 << i) & ar[j])) {
        if (cur > 0) se[i].insert({j - cur, j - 1});
        ans += (1 << i) * c2(cur);
        cur = 0;
      } else
        cur++;
    }
    if (cur > 0) {
      se[i].insert({n + 1 - cur, n + 1 - 1});
      ans += (1 << i) * c2(cur);
    }
  }
  while (m--) {
    long long p, v;
    cin >> p >> v;
    for (long long i = 0; i < M; i++) {
      if (((1 << i) & ar[p]) == ((1 << i) & v)) {
        continue;
      }
      long long cur = ans;
      if (((1 << i) & v)) {
        add(p, i);
      } else {
        sub(p, i);
      }
      long long now = ans;
      long long dif = now - cur;
      dif *= (1 << i);
      ans = dif + cur;
    }
    ar[p] = v;
    cout << ans << "\n";
  }
}