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 inf = 1000000000;
const int MOD = 1000000007;
const double pi = acos(-1.0);
long long solve(set<int> &s, int bit) {
  int last;
  long long ans = 0;
  for (set<int>::iterator it = s.begin(); it != s.end(); ++it) {
    if (it == s.begin()) {
      last = *it;
      continue;
    }
    int len = (*it - last - 1);
    ans += len * 1LL * (len + 1) / 2;
    last = *it;
  }
  return ans * (1LL << bit);
}
const int N = 100009;
int a[N + 1], p[N + 1], v[N + 1], init[N + 1];
long long ans[N + 1];
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = (1); i <= (n); ++i) scanf("%d", &init[i]);
  for (int i = (1); i <= (m); ++i) scanf("%d %d", &p[i], &v[i]);
  long long tot = 0;
  for (int bit = (0); bit <= (18); ++bit) {
    for (int i = (1); i <= (n); ++i) a[i] = init[i];
    set<int> zero;
    zero.insert(0);
    zero.insert(n + 1);
    for (int i = (1); i <= (n); ++i) {
      if (a[i] & (1 << bit))
        ;
      else
        zero.insert(i);
    }
    long long cur = solve(zero, bit);
    tot += cur;
    for (int i = (1); i <= (m); ++i) {
      int pos = p[i];
      int nv = v[i];
      if (a[pos] & (1 << bit))
        if (!(nv & (1 << bit))) {
          set<int>::iterator it = zero.lower_bound(pos);
          set<int>::iterator it1 = it;
          it1--;
          int L = *it1, R = *it;
          long long len1 = (pos - L - 1), len2 = (R - pos - 1),
                    len = (R - L - 1);
          long long t = len * (len + 1) - len1 * (len1 + 1) - len2 * (len2 + 1);
          t /= 2;
          t *= (1LL << bit);
          cur -= t;
          zero.insert(pos);
          a[pos] = nv;
        }
      if (!(a[pos] & (1 << bit)))
        if (nv & (1 << bit)) {
          set<int>::iterator it = zero.upper_bound(pos);
          set<int>::iterator it1 = it;
          it1--;
          --it1;
          int L = *it1, R = *it;
          long long len1 = (pos - L - 1), len2 = (R - pos - 1),
                    len = (R - L - 1);
          long long t = len * (len + 1) - len1 * (len1 + 1) - len2 * (len2 + 1);
          t /= 2;
          t *= (1LL << bit);
          cur += t;
          a[pos] = nv;
          zero.erase(pos);
        }
      ans[i] += cur;
    }
  }
  for (int i = (1); i <= (m); ++i) cout << ans[i] << endl;
}