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;
inline int in() {
  int32_t x;
  scanf("%d", &x);
  return x;
}
inline long long lin() {
  long long x;
  scanf("%lld", &x);
  return x;
}
inline string get() {
  char ch[2000010];
  scanf("%s", ch);
  return ch;
}
inline void read(int *a, int n) {
  for (int i = 0; i < n; i++) a[i] = in();
}
template <class blank>
inline void out(blank x) {
  cout << x << "\n";
  exit(0);
}
const int maxn = 2e5 + 10;
const int maxm = 1e6 + 10;
const int maxlg = 20;
const int base = 29;
const int mod = 1e9 + 7;
const long long INF = 1e18 + 10;
const int SQ = 317 + 5;
int n, q, a[maxn];
struct node {
  int pref[20], suf[20], tot;
  long long res[20];
  node() {
    for (int i = 0; i < 20; i++) pref[i] = suf[i] = res[i] = 0;
    tot = 0;
  }
  inline void reset() {
    for (int i = 0; i < 20; i++) pref[i] = suf[i] = res[i] = 0;
    tot = 0;
  }
} stree[4 * maxn];
inline long long Sum(int n) { return 1LL * n * (n + 1) / 2; }
inline void merge(node &a, node &b, node &c) {
  a.tot = b.tot + c.tot;
  for (int i = 0; i < maxlg; i++) {
    a.pref[i] = b.pref[i] + (b.pref[i] == b.tot ? c.pref[i] : 0);
    a.suf[i] = c.suf[i] + (c.suf[i] == c.tot ? b.suf[i] : 0);
    a.res[i] = b.res[i] + c.res[i] - Sum(b.suf[i]) - Sum(c.pref[i]) +
               Sum(b.suf[i] + c.pref[i]);
  }
}
inline void build(int p = 0, int l = 0, int r = n - 1) {
  if (l == r) {
    for (int i = maxlg - 1; i >= 0; i--) {
      if (a[l] >> i & 1) {
        stree[p].pref[i] = stree[p].suf[i] = stree[p].res[i] = 1;
      }
    }
    stree[p].tot = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build(2 * p + 1, l, mid);
  build(2 * p + 2, mid + 1, r);
  merge(stree[p], stree[2 * p + 1], stree[2 * p + 2]);
}
inline void update(int qx, int val, int p = 0, int l = 0, int r = n - 1) {
  if (l > qx || r < qx) return;
  if (l == r) {
    a[qx] = val;
    stree[p].reset();
    for (int i = maxlg - 1; i >= 0; i--) {
      if (a[l] >> i & 1) {
        stree[p].pref[i] = stree[p].suf[i] = stree[p].res[i] = 1;
      }
    }
    stree[p].tot = 1;
    return;
  }
  int mid = (l + r) >> 1;
  update(qx, val, 2 * p + 1, l, mid), update(qx, val, 2 * p + 2, mid + 1, r);
  merge(stree[p], stree[2 * p + 1], stree[2 * p + 2]);
}
int32_t main() {
  n = in(), q = in();
  read(a, n);
  build();
  while (q--) {
    int id = in() - 1, val = in();
    update(id, val);
    long long res = 0;
    for (int i = 0; i < maxlg; i++) res += 1LL * stree[0].res[i] * (1LL << i);
    cout << res << "\n";
  }
}