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 double PI = acos(-1.0);
const long long MOD = 1000000000 + 7;
const int MAXN = 100000 + 5;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
inline long long readLL() {
  char ch;
  bool flag = false;
  long long a = 0;
  while (!((((ch = getchar()) >= '0') && (ch <= '9')) || (ch == '-')))
    ;
  if (ch != '-') {
    a *= 10;
    a += ch - '0';
  } else {
    flag = true;
  }
  while (((ch = getchar()) >= '0') && (ch <= '9')) {
    a *= 10;
    a += ch - '0';
  }
  if (flag) a = -a;
  return a;
}
inline int read() {
  char ch;
  bool flag = false;
  int a = 0;
  while (!((((ch = getchar()) >= '0') && (ch <= '9')) || (ch == '-')))
    ;
  if (ch != '-') {
    a *= 10;
    a += ch - '0';
  } else {
    flag = true;
  }
  while (((ch = getchar()) >= '0') && (ch <= '9')) {
    a *= 10;
    a += ch - '0';
  }
  if (flag) a = -a;
  return a;
}
const int N = 100005;
int a[N];
set<int> S[20];
int n, m;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1, __END__ = (int)(n); i <= __END__; i++) scanf("%d", &a[i]);
  a[0] = a[n + 1] = 0;
  for (int i = (int)(0), __END__ = (int)(n + 1); i <= __END__; i++) {
    for (int j = 0, __END__ = (int)(20); j < __END__; j++)
      if (((a[i] >> j) & 1) == 0) {
        S[j].insert(i);
      }
  }
  int l, r;
  long long ans = 0;
  set<int>::iterator it;
  for (int i = 1, __END__ = (int)(n); i <= __END__; i++)
    for (int j = 0, __END__ = (int)(20); j < __END__; j++)
      if ((a[i] >> j) & 1) {
        it = S[j].lower_bound(i);
        r = *it;
        l = i;
        ans += (1LL << j) * (r - l);
      }
  while (m--) {
    int x, y;
    scanf("%d%d", &x, &y);
    long long now = 0;
    long long p;
    long long ll;
    long long rr;
    for (int j = 0, __END__ = (int)(20); j < __END__; j++)
      if ((a[x] >> j) & 1) {
        it = S[j].lower_bound(x);
        r = *it;
        --it;
        l = *it;
        p = r - l - 1;
        ll = x - l - 1;
        rr = r - x - 1;
        now += (1LL << j) * (p * (p - 1) / 2) + (1LL << j) -
               (1LL << j) * ll * (ll - 1) / 2 - (1LL << j) * rr * (rr - 1) / 2;
      }
    for (int j = 0, __END__ = (int)(20); j < __END__; j++)
      if (((a[x] >> j) & 1) == 0) {
        S[j].erase(S[j].find(x));
      }
    ans -= now;
    now = 0;
    a[x] = y;
    for (int j = 0, __END__ = (int)(20); j < __END__; j++)
      if ((a[x] >> j) & 1) {
        it = S[j].lower_bound(x);
        r = *it;
        --it;
        l = *it;
        p = r - l - 1;
        ll = x - l - 1;
        rr = r - x - 1;
        now += (1LL << j) * (p * (p - 1) / 2) + (1LL << j) -
               (1LL << j) * ll * (ll - 1) / 2 - (1LL << j) * rr * (rr - 1) / 2;
      }
    for (int j = 0, __END__ = (int)(20); j < __END__; j++)
      if (((a[x] >> j) & 1) == 0) {
        S[j].insert(x);
      }
    ans += now;
    printf("%I64d\n", ans);
  }
  return 0;
}