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[110000];
long long tot;
set<pair<int, int> > S[17];
void Insert(int i, int u) {
  pair<int, int> p[3], pu, pv;
  int n, ii, ok = 0, j, x, y;
  set<pair<int, int> >::iterator it = S[i].upper_bound(pair<int, int>(u, u)),
                                 jt;
  pu = pair<int, int>(-100000000, -100000000);
  pv = pair<int, int>(100000000, 100000000);
  if (it != S[i].end()) {
    pv = *it;
    n = pv.second - pv.first + 1;
    tot -= 1LL * n * (n + 1) / 2 * (1 << i);
    ok = 1;
  }
  if (it != S[i].begin()) {
    it--;
    pu = *it;
    n = pu.second - pu.first + 1;
    tot -= 1LL * n * (n + 1) / 2 * (1 << i);
    S[i].erase(pu);
  }
  if (ok) S[i].erase(pv);
  n = 0;
  p[n++] = pu;
  p[n++] = pair<int, int>(u, u);
  p[n++] = pv;
  for (ii = 0; ii < 3; ii = j) {
    x = p[ii].first;
    y = p[ii].second;
    for (j = ii + 1; j < 3; j++) {
      if (p[j].first == y + 1) {
        y = p[j].second;
      } else
        break;
    }
    if (abs(x) < 110000 && abs(y) < 110000) {
      S[i].insert(pair<int, int>(x, y));
      tot += 1LL * (y - x + 1) * (y - x + 2) / 2 * (1 << i);
    }
  }
}
void Delete(int i, int u) {
  set<pair<int, int> >::iterator it =
      S[i].upper_bound(pair<int, int>(u + 1, -100000000));
  it--;
  pair<int, int> pu;
  long long n;
  pu = *it;
  n = pu.second - pu.first + 1;
  tot -= 1LL * n * (n + 1) / 2 * (1 << i);
  S[i].erase(it);
  if (pu.first <= u - 1) S[i].insert(pair<int, int>(pu.first, u - 1));
  if (pu.second >= u + 1) S[i].insert(pair<int, int>(u + 1, pu.second));
  n = u - pu.first;
  tot += 1LL * n * (n + 1) / 2 * (1 << i);
  n = pu.second - u;
  tot += 1LL * n * (n + 1) / 2 * (1 << i);
}
int main() {
  int N, M, i, j, k, p, v;
  long long n;
  scanf("%d%d", &N, &M);
  for (i = 0; i < N; i++) {
    scanf("%d", a + i);
  }
  for (i = tot = 0; i < 17; i++) {
    S[i].clear();
    for (j = 0; j < N; j++) {
      if (((1 << i) & a[j]) == 0) continue;
      for (k = j + 1; k < N; k++) {
        if ((1 << i) & a[k]) continue;
        break;
      }
      S[i].insert(pair<int, int>(j, k - 1));
      n = k - j;
      tot += (1LL << i) * 1LL * n * (n + 1) / 2;
      j = k;
    }
  }
  for (i = 0; i < M; i++) {
    scanf("%d%d", &p, &v);
    p--;
    for (j = 0; j < 17; j++) {
      if (((1 << j) & v) == ((1 << j) & a[p])) continue;
      if ((1 << j) & v) {
        Insert(j, p);
      } else {
        Delete(j, p);
      }
    }
    printf("%I64d\n", tot);
    a[p] = v;
  }
  return 0;
}