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;
struct trio {
  bool val;
  int l, r;
};
struct duo {
  int l, r;
};
int A[100000 + 5], n;
trio H[17][100000 + 5];
duo tree[17][4 * 100000 + 5];
int min(int a, int b) {
  if (a <= b) return (a);
  return (b);
}
int max(int a, int b) {
  if (a >= b) return (a);
  return (b);
}
void build(int node, int start, int end, int i) {
  if (start == end) {
    if (H[i][start].val) {
      tree[i][node].l = n + 1;
      tree[i][node].r = 0;
    } else
      tree[i][node].l = tree[i][node].r = start;
  } else {
    int mid = (start + end) / 2;
    build(2 * node, start, mid, i);
    build(2 * node + 1, mid + 1, end, i);
    tree[i][node].l = min(tree[i][2 * node].l, tree[i][2 * node + 1].l);
    tree[i][node].r = max(tree[i][2 * node].r, tree[i][2 * node + 1].r);
  }
}
void update(int node, int start, int end, int idx, bool val, int i) {
  if (start == end) {
    H[i][start].val = val;
    if (val) {
      tree[i][node].l = n + 1;
      tree[i][node].r = 0;
    } else {
      tree[i][node].l = tree[i][node].r = start;
    }
  } else {
    int mid = (start + end) / 2;
    if (start <= idx && idx <= mid)
      update(2 * node, start, mid, idx, val, i);
    else
      update(2 * node + 1, mid + 1, end, idx, val, i);
    tree[i][node].l = min(tree[i][2 * node].l, tree[i][2 * node + 1].l);
    tree[i][node].r = max(tree[i][2 * node].r, tree[i][2 * node + 1].r);
  }
}
int queryl(int node, int start, int end, int l, int r, int i) {
  if (r < start || end < l) return (n + 1);
  if (l <= start && end <= r) return (tree[i][node].l);
  int mid = (start + end) / 2;
  int p1 = queryl(2 * node, start, mid, l, r, i);
  int p2 = queryl(2 * node + 1, mid + 1, end, l, r, i);
  return (min(p1, p2));
}
int queryr(int node, int start, int end, int l, int r, int i) {
  if (r < start || end < l) return (0);
  if (l <= start && end <= r) return (tree[i][node].r);
  int mid = (start + end) / 2;
  int p1 = queryr(2 * node, start, mid, l, r, i);
  int p2 = queryr(2 * node + 1, mid + 1, end, l, r, i);
  return (max(p1, p2));
}
int main() {
  int m;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
  for (int i = 0; i < 17; i++) {
    for (int j = 1; j <= n; j++) {
      H[i][j].val = A[j] & 1;
      A[j] >>= 1;
    }
    if (H[i][1].val) H[i][1].l = 1;
    for (int j = 2; j <= n; j++)
      if (H[i][j].val) {
        if (H[i][j - 1].val)
          H[i][j].l = H[i][j - 1].l;
        else
          H[i][j].l = j;
      }
    if (H[i][n].val) H[i][n].r = n;
    for (int j = n - 1; j; j--)
      if (H[i][j].val) {
        if (H[i][j + 1].val)
          H[i][j].r = H[i][j + 1].r;
        else
          H[i][j].r = j;
      }
  }
  long long int sum = 0;
  for (int i = 0; i < 17; i++) {
    long long int hp = 1 << i, csum = 0;
    for (int j = 1; j <= n; j++)
      if (H[i][j].val) {
        long long int d = H[i][j].r - H[i][j].l + 1;
        csum += d * (d + 1) / 2;
        j = H[i][j].r;
      }
    sum += csum * hp;
  }
  for (int i = 0; i < 17; i++) build(1, 1, n, i);
  for (int t = 0; t < m; t++) {
    int p, v;
    scanf("%d %d", &p, &v);
    for (int i = 0; i < 17; i++) {
      bool b = v & 1;
      v >>= 1;
      if (b == H[i][p].val) continue;
      update(1, 1, n, p, b, i);
      long long int hp = 1 << i, cl, cr, csum = 0;
      cl = queryr(1, 1, n, 1, p - 1, i);
      cr = queryl(1, 1, n, p + 1, n, i);
      long long int d = (p - 1) - cl;
      csum -= d * (d + 1) / 2;
      d = cr - (p + 1);
      csum -= d * (d + 1) / 2;
      d = cr - cl - 1;
      csum += d * (d + 1) / 2;
      if (!b) csum = -csum;
      sum += csum * hp;
    }
    printf("%lld\n", sum);
  }
  return (0);
}