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 = 100100, MAXR = 320;
long long n, m, ans, lb, v[MAXN];
bool on[MAXN][20];
long long g(long long x, long long bit) {
  if (x % 2 == 0) return (x / 2ll) * (x + 1ll) * (1ll << bit);
  return ((x + 1ll) / 2ll) * x * (1ll << bit);
}
struct block {
  bool f, a[MAXR];
  long long l, r, id, bit, sz;
  block(long long l, long long r, long long bit, long long aux)
      : l(l), r(r), bit(bit), id(aux), f(0) {
    for (long long i = l, pos = 0; i <= r; i++, pos++)
      a[pos] = on[i][bit], f = (a[pos] == 0 ? 1 : f), sz = pos;
    sz++;
  }
  block(){};
} b[MAXR][20];
void update(long long pos, long long x, long long id, long long bit,
            long long sz) {
  if (b[id][bit].a[pos] == x) return;
  long long lz = -1ll, rz = n;
  for (long long i = pos - 1ll; i >= 0; i--)
    if (b[id][bit].a[i] == 0) {
      lz = MAXR * id + i;
      break;
    }
  if (lz == -1ll && id != 0) {
    long long aux = id - 1ll;
    while (aux >= 0 && b[aux][bit].f == 0ll) aux--;
    if (aux == -1ll)
      lz = -1ll;
    else
      for (long long i = b[aux][bit].sz - 1ll; i >= 0; i--)
        if (b[aux][bit].a[i] == 0) {
          lz = MAXR * aux + i;
          break;
        }
  }
  for (long long i = pos + 1ll; i < sz; i++)
    if (b[id][bit].a[i] == 0) {
      rz = MAXR * id + i;
      break;
    }
  if (rz == n && id != lb) {
    long long aux = id + 1ll;
    while (aux <= lb && b[aux][bit].f == 0ll) aux++;
    if (aux > lb)
      rz = n;
    else
      for (long long i = 0; i < b[aux][bit].sz; i++)
        if (b[aux][bit].a[i] == 0) {
          rz = MAXR * aux + i;
          break;
        }
  }
  b[id][bit].a[pos] = x;
  if (b[id][bit].a[pos] == 1ll) {
    pos = MAXR * id + pos;
    ans -= g(pos - lz - 1ll, bit) + g(rz - pos - 1ll, bit);
    ans += g(rz - lz - 1ll, bit);
  } else {
    pos = MAXR * id + pos;
    ans += g(pos - lz - 1ll, bit) + g(rz - pos - 1ll, bit);
    ans -= g(rz - lz - 1ll, bit);
  }
  bool ok = 0;
  for (long long i = 0; i < sz; i++)
    if (b[id][bit].a[i] == 0) ok = b[id][bit].f = 1ll;
  if (!ok) b[id][bit].f = 0;
}
signed main() {
  scanf("%lld %lld", &n, &m);
  long long auxl = 0, auxr = 0, aux = 0;
  lb = (n - 1ll) / MAXR;
  for (long long i = 0; i < n; i++, auxr++) {
    scanf("%lld", &v[i]);
    for (long long j = 0; j < 20; j++) on[i][j] = ((v[i] >> j) & 1ll);
    if ((i % MAXR == 0 && i != 0) || i == n - 1ll) {
      for (long long j = 0; j < 20; j++)
        b[aux][j] = block(auxl, auxr - (i != n - 1ll), j, aux);
      aux++;
      auxl = i;
    }
  }
  for (long long j = 0; j < 20; j++) {
    vector<long long> k;
    for (long long i = 0; i < n; i++) {
      if (((v[i] >> j) & 1ll) && (i == 0 || !((v[i - 1ll] >> j) & 1ll)))
        k.push_back(i);
      if (((v[i] >> j) & 1ll) && (i == n - 1ll || !((v[i + 1ll] >> j) & 1ll)))
        k.push_back(i);
    }
    if (k.size() == 0) continue;
    for (long long i = 0; i < k.size(); i += 2)
      ans += g(k[i + 1ll] - k[i] + 1ll, j);
  }
  while (m--) {
    long long p, x;
    scanf("%lld %lld", &p, &x), p--;
    for (long long i = 0; i < 20; i++)
      update(p % MAXR, (x >> i) & 1ll, p / MAXR, i, b[p / MAXR][i].sz);
    printf("%lld\n", ans);
  }
}