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;
typedef struct segt {
  long long len, prefix, suffix, ans;
} segmenttree;
segmenttree tree[18][(262144 + 22)];
long long arr[18][(262144 + 22) >> 1];
int n, m;
void splitnum(int index, long long num);
void build(int l, int r, int index);
segmenttree merge_interval(segmenttree t1, segmenttree t2);
void update(int pt, int l, int r, int index, long long val);
long long query();
int main() {
  int i;
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) {
    long long v;
    scanf("%lld", &v);
    splitnum(i, v);
  }
  build(1, n, 1);
  for (i = 1; i <= m; i++) {
    int p;
    long long v;
    scanf("%d%lld", &p, &v);
    update(p, 1, n, 1, v);
    printf("%lld\n", query());
  }
  return 0;
}
long long query() {
  long long ans = 0;
  for (int i = 0; i < 17; i++) {
    ans += (1 << i) * tree[i][1].ans;
  }
  return ans;
}
void update(int pt, int l, int r, int index, long long val) {
  if (l > r) return;
  if (l == r && pt == r) {
    splitnum(pt, val);
    for (int i = 0; i < 17; i++) {
      tree[i][index].len = 1;
      tree[i][index].prefix = tree[i][index].suffix = tree[i][index].ans =
          arr[i][l];
    }
    return;
  }
  int mid = l + (r - l) / 2;
  if (pt <= mid) {
    update(pt, l, mid, index * 2, val);
  } else {
    update(pt, mid + 1, r, index * 2 + 1, val);
  }
  for (int i = 0; i < 17; i++) {
    tree[i][index] = merge_interval(tree[i][index * 2], tree[i][index * 2 + 1]);
  }
}
void splitnum(int index, long long num) {
  int i = 0;
  for (i = 0; i < 17; i++) {
    arr[i][index] = 0;
  }
  i = 0;
  while (num > 0) {
    arr[i++][index] = num % 2;
    num /= 2;
  }
}
segmenttree merge_interval(segmenttree t1, segmenttree t2) {
  segmenttree t;
  t.len = t1.len + t2.len;
  long long central = t1.suffix + t2.prefix;
  t.ans = t1.ans + t2.ans - (t1.suffix * (t1.suffix + 1)) / 2 -
          (t2.prefix * (t2.prefix + 1)) / 2 + (central * (central + 1)) / 2;
  if (t2.suffix == t2.len) {
    t.suffix = t2.suffix + t1.suffix;
  } else {
    t.suffix = t2.suffix;
  }
  if (t1.prefix == t1.len) {
    t.prefix = t1.prefix + t2.prefix;
  } else {
    t.prefix = t1.prefix;
  }
  return t;
}
void build(int l, int r, int index) {
  int i;
  if (l > r) return;
  if (l == r) {
    for (i = 0; i < 17; i++) {
      tree[i][index].len = 1;
      tree[i][index].prefix = tree[i][index].suffix = tree[i][index].ans =
          arr[i][l];
    }
    return;
  }
  int mid = l + (r - l) / 2;
  build(l, mid, index * 2);
  build(mid + 1, r, index * 2 + 1);
  for (i = 0; i < 17; i++) {
    tree[i][index] = merge_interval(tree[i][index * 2], tree[i][index * 2 + 1]);
  }
}