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 N = 100010;
const int BIT = 18;
struct Node {
  int ls, rs;
  bool all;
  long long val;
  Node() {}
  Node(int ls, int rs, bool all, int val)
      : ls(ls), rs(rs), all(all), val(val) {}
};
Node merge(Node a, Node b) {
  Node c;
  c.ls = a.all ? a.ls + b.ls : a.ls;
  c.rs = b.all ? a.rs + b.rs : b.rs;
  c.all = a.all && b.all;
  c.val = a.val + b.val + (long long)a.rs * b.ls;
  return c;
}
Node f[BIT][N << 2];
void update(Node* t, int p, int v, int l, int r, int rt) {
  if (l == r) {
    t[rt] = Node(v, v, v, v);
    return;
  }
  int m = (l + r) >> 1;
  if (p <= m)
    update(t, p, v, l, m, (rt << 1));
  else
    update(t, p, v, m + 1, r, (rt << 1 | 1));
  t[rt] = merge(t[(rt << 1)], t[(rt << 1 | 1)]);
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  memset(f, 0, sizeof(f));
  for (int i = 1; i <= n; i++) {
    int a;
    scanf("%d", &a);
    for (int k = 0; k < BIT; k++) update(f[k], i, (a >> k) & 1, 1, n, 1);
  }
  for (int i = 0; i < m; i++) {
    int p, v;
    scanf("%d%d", &p, &v);
    long long ans = 0;
    for (int k = 0; k < BIT; k++) {
      update(f[k], p, (v >> k) & 1, 1, n, 1);
      ans += f[k][1].val << k;
    }
    printf("%I64d\n", ans);
  }
  return 0;
}