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 int INF = (long long int)1e9 + 10;
const long long int INFLL = (long long int)1e18 + 10;
const long double EPS = 1e-8;
const long double EPSLD = 1e-18;
const long long int MOD = 1e9 + 7;
template <class T>
T &chmin(T &a, const T &b) {
  return a = min(a, b);
}
template <class T>
T &chmax(T &a, const T &b) {
  return a = max(a, b);
}
template <typename T>
struct LazySegtree {
  const T ID = 0;
  const T NONE = INFLL;
  vector<T> node, lazy;
  long long int size;
  inline void push(long long int k, long long int l, long long int r) {
    if (k < size - 1)
      lazy[k * 2 + 1] = lazy[k * 2 + 2] = lazy[k];
    else
      node[k] = lazy[k];
    lazy[k] = NONE;
  }
  void init(long long int n) {
    size = 1;
    while (size < n) size *= 2;
    lazy = vector<T>(size * 2 - 1, NONE);
    node = vector<T>(size * 2 - 1, ID);
  }
  void update(long long int a, long long int b, T x, long long int k,
              long long int l, long long int r) {
    if (a <= l && r <= b) {
      lazy[k] = x;
      push(k, l, r);
    } else if (b <= l || r <= a) {
      return;
    } else {
      if (lazy[k] != NONE) push(k, l, r);
      update(a, b, x, k * 2 + 1, l, (l + r) / 2);
      update(a, b, x, k * 2 + 2, (l + r) / 2, r);
    }
  }
  void update(long long int a, long long int b, T x) {
    update(a, b, x, 0, 0, size);
  }
  T get(long long int a, long long int k, long long int l, long long int r) {
    if (lazy[k] != NONE) push(k, l, r);
    if (r - l == 1) {
      return node[k];
    } else {
      if (a < (l + r) / 2)
        return get(a, k * 2 + 1, l, (l + r) / 2);
      else
        return get(a, k * 2 + 2, (l + r) / 2, r);
    }
  }
  T get(long long int a) { return get(a, 0, 0, size); }
};
const long long int MAX_N = 100010;
long long int n, m;
long long int a[MAX_N];
LazySegtree<long long int> l[20], r[20];
long long int le[MAX_N], ri[MAX_N];
long long int ans = 0;
int main() {
  scanf("%lld %lld", &n, &m);
  for (long long int i = (0); i < (long long int)(n); i++)
    scanf("%lld", &a[i + 1]);
  for (long long int j = (0); j < (long long int)(20); j++) {
    le[0] = 0;
    le[n + 1] = n + 1;
    for (long long int i = (1); i < (long long int)(n + 1); i++) {
      if (a[i] & (1LL << (j)))
        le[i] = le[i - 1];
      else
        le[i] = i;
    }
    l[j].init(n + 2);
    for (long long int i = (0); i < (long long int)(n + 2); i++)
      l[j].update(i, i + 1, le[i]);
    ri[0] = 0;
    ri[n + 1] = n + 1;
    for (long long int i = n; i >= 1; i--) {
      if (a[i] & (1LL << (j)))
        ri[i] = ri[i + 1];
      else
        ri[i] = i;
    }
    r[j].init(n + 2);
    for (long long int i = (0); i < (long long int)(n + 2); i++)
      r[j].update(i, i + 1, ri[i]);
    for (long long int i = (1); i < (long long int)(n + 1); i++)
      ans += (ri[i] - i) * (1LL << (j));
  }
  for (long long int query_cnt = (0); query_cnt < (long long int)(m);
       query_cnt++) {
    long long int p, v;
    scanf("%lld %lld", &p, &v);
    for (long long int j = (0); j < (long long int)(20); j++) {
      if ((v & (1LL << (j))) && !(a[p] & (1LL << (j)))) {
        long long int tor = r[j].get(p + 1);
        long long int tol = l[j].get(p - 1);
        r[j].update(tol + 1, p + 1, tor);
        l[j].update(p, tor, tol);
        ans += (tor - p) * (p - tol) * (1LL << (j));
      }
      if (!(v & (1LL << (j))) && (a[p] & (1LL << (j)))) {
        long long int tor = r[j].get(p);
        long long int tol = l[j].get(p);
        r[j].update(tol + 1, p + 1, p);
        l[j].update(p, tor, p);
        ans -= (tor - p) * (p - tol) * (1LL << (j));
      }
    }
    a[p] = v;
    printf("%lld\n", ans);
  }
  return 0;
}