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>
const int N = 1e5 + 5, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double PI = acos(-1), EPS = 1e-9;
using namespace std;
namespace fast_IO {
long long read() {
  long long x = 0;
  char c;
  bool flag = false;
  while ((c = getchar()) == ' ' || c == '\n' || c == '\r')
    ;
  if (c == '-')
    flag = true;
  else
    x = c ^ 48;
  while ((c = getchar()) >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48);
  if (flag) return -x;
  return x;
}
void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) write(x / 10);
  putchar(x % 10 ^ 48);
}
}  // namespace fast_IO
int suf[N][18], a[N], pre[N][18];
struct Segment_Tree {
  int id;
  struct Node {
    int l, r;
    long long sum, del;
    int pre, tag;
  } tree[N << 2];
  void pushup(int x) { tree[x].sum = tree[x << 1].sum + tree[x << 1 | 1].sum; }
  void pushdown(int x) {
    if (!tree[x].del) return;
    tree[x << 1].sum += tree[x].del * (tree[x << 1].r - tree[x << 1].l + 1);
    tree[x << 1 | 1].sum +=
        tree[x].del * (tree[x << 1 | 1].r - tree[x << 1 | 1].l + 1);
    tree[x << 1].del += tree[x].del;
    tree[x << 1 | 1].del += tree[x].del;
    tree[x].del = 0;
  }
  void pushdown2(int x) {
    if (!tree[x].tag) return;
    tree[x << 1].tag = tree[x << 1 | 1].tag = tree[x].tag;
    tree[x << 1].pre = tree[x << 1 | 1].pre = tree[x].tag;
    tree[x].tag = 0;
  }
  void build(int x, int l, int r) {
    tree[x].l = l, tree[x].r = r;
    if (l == r) {
      tree[x].sum = suf[l][id];
      tree[x].pre = pre[l][id];
      return;
    }
    int mid = l + r >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    pushup(x);
  }
  void update(int x, int l, int r, long long data) {
    if (tree[x].l == l && tree[x].r == r) {
      tree[x].del += data;
      tree[x].sum += (r - l + 1) * data;
      return;
    }
    pushdown(x);
    int mid = tree[x].l + tree[x].r >> 1;
    if (r <= mid)
      update(x << 1, l, r, data);
    else if (l > mid)
      update(x << 1 | 1, l, r, data);
    else
      update(x << 1, l, mid, data), update(x << 1 | 1, mid + 1, r, data);
    pushup(x);
  }
  void change(int x, int l, int r, int p) {
    if (tree[x].l == l && tree[x].r == r) {
      tree[x].tag = p;
      tree[x].pre = p;
      return;
    }
    pushdown2(x);
    int mid = tree[x].l + tree[x].r >> 1;
    if (r <= mid)
      change(x << 1, l, r, p);
    else if (l > mid)
      change(x << 1 | 1, l, r, p);
    else
      change(x << 1, l, mid, p), change(x << 1 | 1, mid + 1, r, p);
  }
  long long query(int x, int l, int r) {
    if (tree[x].l == l && tree[x].r == r) return tree[x].sum;
    pushdown(x);
    int mid = tree[x].l + tree[x].r >> 1;
    if (r <= mid) return query(x << 1, l, r);
    if (l > mid) return query(x << 1 | 1, l, r);
    return query(x << 1, l, mid) + query(x << 1 | 1, mid + 1, r);
  }
  int query(int x, int p) {
    if (tree[x].l == tree[x].r) return tree[x].pre;
    pushdown2(x);
    int mid = tree[x].l + tree[x].r >> 1;
    if (p <= mid) return query(x << 1, p);
    return query(x << 1 | 1, p);
  }
} t[18];
int main() {
  int n = fast_IO::read(), m = fast_IO::read();
  for (int i = 1; i <= n; ++i) a[i] = fast_IO::read();
  for (int j = 0; j < 18; ++j) {
    for (int i = n; i; --i) {
      if (a[i] & (1 << j))
        suf[i][j] = suf[i + 1][j] + 1;
      else
        suf[i][j] = 0;
    }
    for (int i = 1; i <= n; ++i) {
      if (a[i - 1] & (1 << j))
        pre[i][j] = pre[i - 1][j];
      else
        pre[i][j] = i;
    }
  }
  for (int i = 0; i < 18; ++i) t[i].id = i, t[i].build(1, 1, n);
  while (m--) {
    int p = fast_IO::read(), v = fast_IO::read();
    for (int i = 0; i < 18; ++i) {
      if ((v & (1 << i)) == (a[p] & (1 << i))) continue;
      if (v & (1 << i)) {
        long long del = p < n ? t[i].query(1, p + 1, p + 1) : 0;
        int loc = t[i].query(1, p - 1);
        if (!(a[p - 1] & (1 << i))) loc = p;
        ++del;
        t[i].update(1, loc, p, del);
        t[i].change(1, p, p + del - 1, loc);
      } else {
        long long del = t[i].query(1, p, p);
        int loc = t[i].query(1, p);
        t[i].update(1, loc, p, -del);
        if (del > 1) t[i].change(1, p + 1, p + del - 1, p + 1);
        t[i].change(1, p, p, p);
      }
    }
    a[p] = v;
    long long ans = 0;
    for (int i = 0; i < 18; ++i) ans += t[i].query(1, 1, n) * (1 << i);
    printf("%lld\n", ans);
  }
  return 0;
}