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 MaxN = 100000 + 10, MaxLog = 17;
inline int lowbit(int x) { return x & -x; }
struct BIT {
  int arr[MaxN], size;
  void add(int wz) {
    for (int i = wz; i <= size; i += lowbit(i)) ++arr[i];
  }
  void del(int wz) {
    for (int i = wz; i <= size; i += lowbit(i)) --arr[i];
  }
  int operator[](const int index) const {
    int ret = 0;
    for (int i = index; i > 0; i -= lowbit(i)) ret += arr[i];
    return ret;
  }
  void init(int _sz) {
    size = _sz;
    for (int i = 1; i <= size; ++i) arr[i] = 0;
  }
} bit[MaxLog];
int n, m;
long long ans;
int lower(BIT &t, int st, int en) {
  int ved = t[en], mid, ed = en;
  if (ved - t[en - 1] == 0) return en + 1;
  --st;
  ++en;
  while (st + 1 < en) {
    mid = (st + en) >> 1;
    if (ved - t[mid - 1] == ed - mid + 1)
      en = mid;
    else
      st = mid;
  }
  return en;
}
int upper(BIT &t, int st, int en) {
  int vsr = t[st - 1], sr = st, mid;
  if (t[st] - vsr == 0) return st - 1;
  --st;
  ++en;
  while (st + 1 < en) {
    mid = (st + en) >> 1;
    if (t[mid] - vsr == mid - sr + 1)
      st = mid;
    else
      en = mid;
  }
  return st;
}
void update(int wz, BIT &t, int v, int p) {
  if (t[wz] - t[wz - 1] == v) return;
  int st, en, l, r;
  st = lower(t, 1, wz - 1);
  en = upper(t, wz + 1, n);
  l = wz - st;
  r = en - wz;
  if (v == 1) {
    ans -= (((long long)l * (long long)(l + 1) +
             (long long)r * (long long)(r + 1)) /
            2LL) *
           (long long)(1 << p);
    ans += (((long long)(l + r + 1) * (long long)(l + r + 2)) / 2LL) *
           (long long)(1 << p);
    t.add(wz);
  } else {
    ans -= (((long long)(l + r + 1) * (long long)(l + r + 2)) / 2LL) *
           (long long)(1 << p);
    ans += (((long long)l * (long long)(l + 1) +
             (long long)r * (long long)(r + 1)) /
            2LL) *
           (long long)(1 << p);
    t.del(wz);
  }
}
void update(int wz, int v) {
  for (int i = 0; i < MaxLog; ++i) update(wz, bit[i], (v >> i) & 1, i);
}
void init() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < MaxLog; ++i) bit[i].init(n);
  int v;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &v);
    update(i, v);
  }
}
void solve() {
  int w, v;
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &w, &v);
    update(w, v);
    cout << ans << endl;
  }
}
int main() {
  init();
  solve();
  return 0;
}