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 int LOG = 17;
int MUL = 1;
long long ans[LOG], F[(1 << 18)];
long long f(long long x) { return F[x]; }
struct node {
  int L, R, size;
  bool allFill = 0;
  long long midScore = 0;
};
template <typename T>
class SegTree {
 public:
  vector<T> t;
  T identity;
  T (*combine)(T, T);
  int size;
  void init(T (*op)(T, T), T e, int n, T* a) {
    combine = op;
    identity = e;
    t.assign(2 * n, e);
    for (int i = 0; i < n; i++) t[i + n] = a[i];
    size = n;
    build();
  }
  void build() {
    for (int i = size - 1; i > 0; i--) t[i] = combine(t[i << 1], t[i << 1 | 1]);
  }
  T query(int l, int r) {
    T lt = identity;
    T rt = identity;
    for (l += size, r += size; l <= r; r >>= 1, l >>= 1) {
      if (l & 1) lt = combine(lt, t[l++]);
      if (!(r & 1)) rt = combine(t[r--], rt);
    }
    return combine(lt, rt);
  }
  void update(int p, T v) {
    for (t[p += size] = v; p >>= 1;) t[p] = combine(t[p << 1], t[p << 1 | 1]);
  }
};
node merge(node f1, node f2) {
  node tem;
  tem.size = f1.size + f2.size;
  if (f1.allFill && f2.allFill) {
    tem.allFill = 1;
    tem.L = -1;
    tem.R = -1;
    tem.midScore = -1;
    return tem;
  }
  if (f1.allFill) {
    tem.L = f1.size + f2.L;
    tem.R = f2.R;
    tem.midScore = f2.midScore;
    tem.allFill = 0;
    return tem;
  }
  if (f2.allFill) {
    tem.R = f2.size + f1.R;
    tem.L = f1.L;
    tem.midScore = f1.midScore;
    tem.allFill = 0;
    return tem;
  }
  tem.L = f1.L;
  tem.R = f2.R;
  tem.midScore = f1.midScore + f2.midScore + f(f1.R + f2.L);
  tem.allFill = 0;
  return tem;
}
long long valx(node phew) {
  if (phew.allFill) {
    return f(phew.size);
  }
  return f(phew.L) + f(phew.R) + phew.midScore;
}
node toPass[LOG][102000];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int N, M;
  cin >> N >> M;
  for (int i = 0; i <= N; i++) {
    F[i] = F[i - 1] + i;
  }
  vector<int> A(N);
  node one;
  one.L = 0, one.R = 0, one.allFill = 1, one.size = 1, one.midScore = 0;
  node zero;
  zero.L = 0, zero.R = 0, zero.allFill = 0, zero.size = 1, zero.midScore = 0;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    A[i] /= MUL;
    for (int bit = 0; bit < LOG; bit++) {
      if (A[i] & (1 << bit)) {
        toPass[bit][i] = one;
      } else {
        toPass[bit][i] = zero;
      }
    }
  }
  node id;
  id.L = 0;
  id.R = 0;
  id.size = 0;
  id.allFill = 0;
  id.midScore = 0;
  SegTree<node> seg[LOG];
  for (int i = 0; i < LOG; i++) {
    seg[i].init(merge, id, N, toPass[i]);
  }
  int cnt = 0;
  while (M--) {
    int ind, val;
    cin >> ind >> val;
    ind--;
    val /= MUL;
    for (int bit = 0; bit < LOG; bit++) {
      if (val & (1 << bit)) {
        seg[bit].update(ind, one);
      } else {
        seg[bit].update(ind, zero);
      }
    }
    long long ret = 0;
    for (int bit = 0; bit < LOG; bit++) {
      ret += (1LL << bit) * valx(seg[bit].query(0, N - 1));
    }
    cout << ret << '\n';
  }
  cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n";
  return 0;
}