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;
const long long maxn = 1e5 + 500;
const long long mod = 1e9 + 7;
const long long inf = 1e9 + 500;
set<long long> sar[17];
set<long long>::iterator sarg;
set<long long>::iterator sarb;
set<long long>::iterator tahg;
set<long long>::iterator tahb;
set<long long> tah[17];
long long a[maxn];
long long ans = 0;
long long nn;
long long mos(long long a) { return a * (a + 1) / 2; }
void update(long long p, long long v) {
  for (long long i = 0; i < 17; i++) {
    long long z = (1 << i);
    bool bit = ((v >> i) & 1);
    if ((((a[p]) >> i) & 1) == bit) {
      continue;
    }
    if (!bit) {
      sarg = sar[i].upper_bound(p);
      sarg--;
      long long s = (*sarg);
      long long t = (*(tah[i].lower_bound(p)));
      ans -= mos(t - s + 1) * z;
      ans += mos(t - p) * z;
      ans += mos(p - s) * z;
      if (s != p) {
        tah[i].insert(p - 1);
      } else {
        sar[i].erase(p);
      }
      if (t != p) {
        sar[i].insert(p + 1);
      } else {
        tah[i].erase(p);
      }
    } else {
      if ((((a[p - 1]) >> i) & 1) && (((a[p + 1]) >> i) & 1)) {
        tah[i].erase(p - 1);
        sar[i].erase(p + 1);
        sarg = sar[i].lower_bound(p);
        sarg--;
        long long sarr = (*sarg);
        long long tahh = (*((tah[i].lower_bound(p))));
        ans -= mos(tahh - p) * z;
        ans -= mos(p - sarr) * z;
        ans += mos(tahh - sarr + 1) * z;
      }
      if ((((a[p - 1]) >> i) & 1) == 0 && (((a[p + 1]) >> i) & 1)) {
        sar[i].erase(p + 1);
        sar[i].insert(p);
        long long tahh = (*((tah[i].lower_bound(p))));
        ans -= mos(tahh - p) * z;
        ans += mos(tahh - p + 1) * z;
      }
      if ((((a[p - 1]) >> i) & 1) && (((a[p + 1]) >> i) & 1) == 0) {
        tah[i].erase(p - 1);
        tah[i].insert(p);
        sarg = sar[i].lower_bound(p);
        sarg--;
        long long sarr = (*sarg);
        ans -= mos(p - sarr) * z;
        ans += mos(p - sarr + 1) * z;
      }
      if ((((a[p - 1]) >> i) & 1) == 0 && (((a[p + 1]) >> i) & 1) == 0) {
        ans += z;
        tah[i].insert(p);
        sar[i].insert(p);
      }
    }
  }
  a[p] = v;
}
int main() {
  long long n, m;
  cin >> n >> m;
  nn = n;
  if (n == 1) {
    long long v;
    cin >> v;
    for (long long i = 0; i < m; i++) {
      cin >> v >> v;
      cout << v << endl;
    }
    return 0;
  }
  for (long long i = 1; i <= n; i++) {
    long long v;
    cin >> v;
    update(i, v);
  }
  while (m--) {
    long long p, v;
    cin >> p >> v;
    update(p, v);
    cout << ans << endl;
  }
}