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 interval {
  int l, r;
  bool operator<(const interval &t) const { return r < t.r; }
};
set<interval> itree[20];
set<interval>::iterator l, r;
long long ans;
long long f(int type, int num) {
  return (1LL << type) * ((num + 1LL) * num) / 2;
}
void add(int type, int pos, int val) {
  interval unit = {pos, pos};
  l = r = itree[type].lower_bound(unit);
  if (val == 0) {
    if (r->l <= pos && pos <= r->r) {
      interval new_left = {r->l, pos - 1}, new_right = {pos + 1, r->r};
      ans -= f(type, (r->r) - (r->l) + 1);
      ans += f(type, new_left.r - new_left.l + 1);
      ans += f(type, new_right.r - new_right.l + 1);
      itree[type].erase(r);
      if (new_left.l <= new_left.r) itree[type].insert(new_left);
      if (new_right.l <= new_right.r) itree[type].insert(new_right);
    }
  } else {
    if (r->l <= pos && pos <= r->r) {
      return;
    }
    if (!itree[type].empty()) {
      if (l != itree[type].begin() && (--l)->r == pos - 1) {
        unit.l = l->l;
        ans -= f(type, l->r - l->l + 1);
        itree[type].erase(l);
      }
      if (r != itree[type].end() && r->l == pos + 1) {
        unit.r = r->r;
        ans -= f(type, r->r - r->l + 1);
        itree[type].erase(r);
      }
    }
    itree[type].insert(unit);
    ans += f(type, unit.r - unit.l + 1);
  }
}
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    int a;
    cin >> a;
    for (int j = 0; j < 20; ++j) {
      if (a % 2 != 0) add(j, i, a % 2);
      a /= 2;
    }
  }
  for (int i = 0; i < m; ++i) {
    int pos, val;
    cin >> pos >> val;
    for (int j = 0; j < 20; ++j) {
      add(j, pos, val % 2);
      val /= 2;
    }
    cout << ans << '\n';
  }
}