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 MAXN = 100000 + 2;
const int N = 17;
inline long long cal(int x) { return 1LL * x * (x + 1) / 2; }
struct Node {
  int vl, vr;
  long long vs;
  Node() {}
  Node(int _vl, int _vr, long long _vs) : vl(_vl), vr(_vr), vs(_vs) {}
  Node merge(const Node &a, const Node &b, const int l, const int r) {
    Node res(-1, -1, 0);
    res.vl = a.vl, res.vr = b.vr;
    res.vs = a.vs + b.vs;
    if (a.vr != -1 && b.vl != -1) {
      int m = l + r >> 1;
      res.vs -= cal(m - a.vr + 1);
      res.vs -= cal(b.vl - m);
      res.vs += cal(b.vl - a.vr + 1);
      if (a.vl >= a.vr) res.vl = b.vl;
      if (b.vr != -1 && b.vl >= b.vr) res.vr = a.vr;
    }
    return res;
  }
};
Node seg[N][MAXN << 2];
int a[MAXN];
long long pow2[N];
void build(int p, int l, int r, int rt) {
  if (l == r) {
    if (a[l] & (1 << p))
      seg[p][rt] = Node(l, l, 1);
    else
      seg[p][rt] = Node(-1, -1, 0);
    return;
  }
  int m = l + r >> 1;
  build(p, l, m, rt << 1);
  build(p, m + 1, r, rt << 1 | 1);
  seg[p][rt] = seg[p][rt].merge(seg[p][rt << 1], seg[p][rt << 1 | 1], l, r);
}
void update(int p, int pos, int add, int l, int r, int rt) {
  if (l == r) {
    if (add == 0)
      seg[p][rt] = Node(-1, -1, 0);
    else
      seg[p][rt] = Node(l, l, 1);
    return;
  }
  int m = l + r >> 1;
  if (pos <= m)
    update(p, pos, add, l, m, rt << 1);
  else
    update(p, pos, add, m + 1, r, rt << 1 | 1);
  seg[p][rt] = seg[p][rt].merge(seg[p][rt << 1], seg[p][rt << 1 | 1], l, r);
}
void solve(int n, int q) {
  pow2[0] = 1;
  for (int i = 1; i < N; ++i) pow2[i] = pow2[i - 1] * 2;
  for (int i = 0; i < N; ++i) build(i, 1, n, 1);
  while (q--) {
    int p, v;
    scanf("%d %d", &p, &v);
    for (int i = 0; i < N; ++i) {
      if ((a[p] & (1 << i)) && (v & (1 << i)) == 0)
        update(i, p, 0, 1, n, 1);
      else if ((a[p] & (1 << i)) == 0 && (v & (1 << i)))
        update(i, p, 1, 1, n, 1);
    }
    a[p] = v;
    long long ans = 0;
    for (int i = 0; i < N; ++i) ans += seg[i][1].vs * pow2[i];
    printf("%lld\n", ans);
  }
}
int main() {
  int n, q;
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  solve(n, q);
  return 0;
}