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 B = 20;
const int N = 1e5 + 7;
int n, m, a[N];
struct ND {
  int l0, r0;
  ND() {}
  ND(int l0, int r0) : l0(l0), r0(r0) {}
  void init(int p, int v) {
    l0 = v == 0 ? p : n + 1;
    r0 = v == 0 ? p : 0;
  }
  void merge(const ND &a, const ND &b) {
    l0 = min(a.l0, b.l0);
    r0 = max(a.r0, b.r0);
  }
};
struct Tree {
  static const int N = ::N << 2;
  ND nd[N];
  void chg(int o, int l, int r, int qx, int qv) {
    if (l == r) {
      nd[o].init(qx, qv);
      return;
    }
    int mid = l + r >> 1;
    if (qx <= mid)
      chg(o << 1, l, mid, qx, qv);
    else
      chg(o << 1 | 1, mid + 1, r, qx, qv);
    nd[o].merge(nd[o << 1], nd[o << 1 | 1]);
  }
  ND qry(int o, int l, int r, int ql, int qr) {
    if (ql <= l && qr >= r) return nd[o];
    int mid = l + r >> 1;
    ND qryl(n + 1, 0);
    if (ql <= mid) qryl = qry(o << 1, l, mid, ql, qr);
    ND qryr(n + 1, 0);
    if (qr > mid) qryr = qry(o << 1 | 1, mid + 1, r, ql, qr);
    ND ret;
    ret.merge(qryl, qryr);
    return ret;
  }
} tree[B];
long long dc(int len) { return 1ll * (len + 1) * len / 2; }
long long getv(int p, int vv) {
  long long ret = 0;
  for (int b = (0); b < (B); ++b) {
    int v = vv >> b & 1;
    int lenl = p - 1 - (p > 1 ? tree[b].qry(1, 1, n, 1, p - 1).r0 : 0);
    int lenr = (p < n ? tree[b].qry(1, 1, n, p + 1, n).l0 : n + 1) - p - 1;
    long long tmp = v == 0 ? dc(lenl) + dc(lenr) : dc(lenl + lenr + 1);
    ret += tmp * (1 << b);
  }
  return ret;
}
void solve() {
  for (int i = (1); i < (n + 1); ++i) scanf("%d", &a[i]);
  for (int i = (1); i < (n + 1); ++i)
    for (int b = (0); b < (B); ++b) tree[b].chg(1, 1, n, i, a[i] >> b & 1);
  long long ans = 0;
  for (int b = (0); b < (B); ++b) {
    int tmp = 0;
    for (int i = (1); i < (n + 2); ++i)
      if (a[i] >> b & 1)
        tmp++;
      else {
        ans += dc(tmp) * (1 << b);
        tmp = 0;
      }
  }
  while (m--) {
    int p, v;
    scanf("%d%d", &p, &v);
    ans += -getv(p, a[p]) + getv(p, v);
    a[p] = v;
    for (int b = (0); b < (B); ++b) tree[b].chg(1, 1, n, p, a[p] >> b & 1);
    printf("%lld\n", ans);
  }
}
int main() {
  while (~scanf("%d%d", &n, &m)) solve();
  return 0;
}