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 maxn = 1e5 + 10, lg = 20;
long long a[maxn];
struct data {
  long long l, r, t, len;
  data() : l(0), r(0), t(0), len(0) {}
  data(long long a, long long b, long long c, long long d)
      : l(a), r(b), t(c), len(d) {}
  data operator+(const data &d) const {
    data ret;
    ret.len = len + d.len;
    if (l == len && d.r == d.len) {
      ret.l = ret.r = len + d.len;
      ret.t = ret.l * (ret.l + 1) / 2;
      return ret;
    }
    if (l == len) {
      ret.l = d.l + l;
      ret.r = d.r;
      ret.t = d.t - d.l * (d.l + 1) / 2;
      ret.t += ret.l * (ret.l + 1) / 2;
      return ret;
    }
    if (d.r == d.len) {
      ret.r = d.r + r;
      ret.l = l;
      ret.t = t - r * (r + 1) / 2;
      ret.t += ret.r * (ret.r + 1) / 2;
      return ret;
    }
    ret.l = l;
    ret.r = d.r;
    ret.t = t + d.t;
    ret.t -= r * (r + 1) / 2;
    ret.t -= d.l * (d.l + 1) / 2;
    ret.t += (d.l + r) * (d.l + r + 1) / 2;
    return ret;
  }
};
struct SegmentTree {
  static SegmentTree mem[400000];
  static SegmentTree *ptr;
  data val[lg];
  SegmentTree *lc, *rc;
  SegmentTree() {}
  SegmentTree(long long L, long long R) {
    lc = rc = nullptr;
    if (L == R) {
      for (long long i = 0; i < lg; ++i) {
        long long bit = (a[L] >> i) & 1;
        val[i] = data(bit, bit, bit, 1);
      }
      return;
    }
    lc = new (ptr++) SegmentTree(L, ((L + R) >> 1));
    rc = new (ptr++) SegmentTree(((L + R) >> 1) + 1, R);
    pull();
  }
  void pull() {
    for (long long i = 0; i < lg; ++i) val[i] = lc->val[i] + rc->val[i];
  }
  void modify(long long L, long long R, long long x, long long v) {
    if (L == R) {
      for (long long i = 0; i < lg; ++i) {
        long long bit = (v >> i) & 1;
        val[i] = data(bit, bit, bit, 1);
      }
      return;
    }
    if (x <= ((L + R) >> 1))
      lc->modify(L, ((L + R) >> 1), x, v);
    else
      rc->modify(((L + R) >> 1) + 1, R, x, v);
    pull();
  }
} * st, SegmentTree::mem[400000], *SegmentTree::ptr = mem;
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  long long n, m;
  cin >> n >> m;
  for (long long i = 1; i <= n; ++i) cin >> a[i];
  st = new (SegmentTree::ptr++) SegmentTree(1, n);
  while (m--) {
    long long p, v;
    cin >> p >> v;
    st->modify(1, n, p, v);
    unsigned long long ans = 0;
    for (long long i = 0; i < lg; ++i) ans += st->val[i].t * (1 << i);
    cout << ans << '\n';
  }
  return 0;
}