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[100500][20];
set<pair<int, int> > b[20];
const int inf = int(1e9);
long long change(int pos, int bit) {
  long long res = 0;
  if (a[pos][bit] == 1) {
    set<pair<int, int> >::iterator it = b[bit].lower_bound(make_pair(pos, inf));
    it--;
    int x = it->first;
    int y = it->second;
    b[bit].erase(it);
    long long len = y - x + 1;
    res -= len * (len + 1) / 2;
    if (x != pos) {
      b[bit].insert(make_pair(x, pos - 1));
      long long len = pos - x;
      res += len * (len + 1) / 2;
    }
    if (y != pos) {
      b[bit].insert(make_pair(pos + 1, y));
      long long len = y - pos;
      res += len * (len + 1) / 2;
    }
  } else {
    set<pair<int, int> >::iterator it = b[bit].lower_bound(make_pair(pos, inf));
    int x = pos;
    int y = pos;
    if (it != b[bit].end())
      if (it->first == y + 1) {
        int len = it->second - it->first + 1;
        res -= len * (len + 1) / 2;
        y = it->second;
        set<pair<int, int> >::iterator it2 = it;
        it++;
        b[bit].erase(it2);
      }
    if (it != b[bit].begin()) {
      it--;
      if (it->second == x - 1) {
        long long len = it->second - it->first + 1;
        res -= len * (len + 1) / 2;
        x = it->first;
        b[bit].erase(it);
      }
    }
    long long len = y - x + 1;
    res += len * (len + 1) / 2;
    b[bit].insert(make_pair(x, y));
  }
  a[pos][bit] = 1 - a[pos][bit];
  res <<= bit;
  return res;
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    int k = 0;
    while (x) {
      a[i][k++] = x & 1;
      x /= 2;
    }
  }
  long long s = 0;
  for (int bit = 0; bit < 20; bit++) {
    int i = 0;
    while (i < n) {
      if (a[i][bit] == 0) {
        i++;
        continue;
      }
      int j = i + 1;
      while (j < n && a[j][bit]) j++;
      b[bit].insert(make_pair(i, j - 1));
      long long t = 1 << bit;
      int len = j - i;
      t *= len;
      t *= len + 1;
      t /= 2;
      s += t;
      i = j;
    }
  }
  for (int i = 0; i < m; i++) {
    int p, v;
    scanf("%d%d", &p, &v);
    p--;
    for (int bit = 0; bit < 20; bit++) {
      if (a[p][bit] != (v & 1)) s += change(p, bit);
      v /= 2;
    }
    printf("%I64d\n", s);
  }
  return 0;
}