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;
long long binpow(long long a, long long b) {
  a %= 1000000007;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % 1000000007;
    a = a * a % 1000000007;
    b >>= 1;
  }
  return res;
}
bool is_composite[100005];
long long int lp[100005];
vector<long long int> prime;
void sieve(int n) {
  std::fill(is_composite, is_composite + n, false);
  for (int i = 2; i < n; ++i) {
    if (!is_composite[i]) {
      prime.push_back(i);
      lp[i] = i;
    }
    for (int j = 0; j < prime.size() && i * prime[j] < n; ++j) {
      is_composite[i * prime[j]] = true;
      lp[i * prime[j]] = prime[j];
      if (i % prime[j] == 0) break;
    }
  }
}
long long int t[21][400005][3];
vector<long long int> v1[21];
void build(long long int v, long long int tl, long long int tr,
           long long int bit) {
  if (tl == tr) {
    t[bit][v][0] = v1[bit][tl];
    t[bit][v][1] = v1[bit][tl];
    t[bit][v][2] = v1[bit][tl];
  } else {
    long long int tm = (tl + tr) / 2;
    build(v * 2, tl, tm, bit);
    build(v * 2 + 1, tm + 1, tr, bit);
    t[bit][v][0] = t[bit][v * 2][0];
    if (t[bit][v * 2][0] == (tm - tl + 1)) {
      t[bit][v][0] += t[bit][v * 2 + 1][0];
    }
    t[bit][v][1] = t[bit][v * 2 + 1][1];
    if (t[bit][v * 2 + 1][1] == (tr - tm)) {
      t[bit][v][1] += t[bit][v * 2][1];
    }
    t[bit][v][2] = t[bit][v * 2][2] + t[bit][v * 2 + 1][2];
    t[bit][v][2] += t[bit][v * 2][1] * t[bit][v * 2 + 1][0];
  }
}
void update(long long int v, long long int tl, long long int tr,
            long long int pos, long long int new_val, long long int bit) {
  if (tl == tr) {
    t[bit][v][0] = new_val;
    t[bit][v][1] = new_val;
    t[bit][v][2] = new_val;
  } else {
    long long int tm = (tl + tr) / 2;
    if (pos <= tm)
      update(v * 2, tl, tm, pos, new_val, bit);
    else
      update(v * 2 + 1, tm + 1, tr, pos, new_val, bit);
    t[bit][v][0] = t[bit][v * 2][0];
    if (t[bit][v * 2][0] == (tm - tl + 1)) {
      t[bit][v][0] += t[bit][v * 2 + 1][0];
    }
    t[bit][v][1] = t[bit][v * 2 + 1][1];
    if (t[bit][v * 2 + 1][1] == (tr - tm)) {
      t[bit][v][1] += t[bit][v * 2][1];
    }
    t[bit][v][2] = t[bit][v * 2][2] + t[bit][v * 2 + 1][2];
    t[bit][v][2] += t[bit][v * 2][1] * t[bit][v * 2 + 1][0];
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int n, m, i, j, a, ind, val, ans;
  cin >> n >> m;
  for (j = 0; j < 20; j++) {
    v1[j].push_back(0);
  }
  for (i = 0; i < n; i++) {
    cin >> a;
    for (j = 0; j < 20; j++) {
      v1[j].push_back((a >> j) & 1);
    }
  }
  for (j = 0; j < 20; j++) {
    build(1, 1, n, j);
  }
  while (m--) {
    cin >> ind >> val;
    ans = 0;
    for (i = 0; i < 20; i++) {
      update(1, 1, n, ind, ((val >> i) & 1), i);
      ans += (1 << i) * t[i][1][2];
    }
    cout << ans << endl;
  }
}