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 N = (int)1e5, N_BIT = 17;
set<pair<int, int> > bitPart[N_BIT];
int a[N];
int main() {
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; ++i) cin >> a[i];
  long long res = 0;
  for (int p = 0; p < N_BIT; ++p) {
    for (int i = 0; i < n;) {
      if ((a[i] & 1 << p) != 0) {
        int j = i;
        while (j < n && (a[j] & 1 << p) != 0) ++j;
        bitPart[p].insert(make_pair(i, j));
        res += ((j - i) * (j - i + 1LL) / 2) << p;
        i = j;
      } else
        ++i;
    }
  }
  while (m-- > 0) {
    int i, v;
    cin >> i >> v;
    --i;
    for (int p = 0; p < N_BIT; ++p)
      if ((a[i] & 1 << p) != (v & 1 << p)) {
        set<pair<int, int> >::iterator after =
            bitPart[p].upper_bound(make_pair(i + 1, i + 1));
        if ((v & 1 << p) != 0) {
          int newLeft = i, newRight = i + 1;
          if (after != bitPart[p].begin()) {
            set<pair<int, int> >::iterator before = after;
            --before;
            if (before->second == newLeft) {
              int beforeLen = before->second - before->first;
              res -= (beforeLen * (beforeLen + 1LL) / 2) << p;
              newLeft = before->first;
              bitPart[p].erase(before);
            }
          }
          if (after != bitPart[p].end() && after->first == newRight) {
            int afterLen = after->second - after->first;
            res -= (afterLen * (afterLen + 1LL) / 2) << p;
            newRight = after->second;
            bitPart[p].erase(after);
          }
          res += ((newRight - newLeft) * (newRight - newLeft + 1LL) / 2) << p;
          bitPart[p].insert(make_pair(newLeft, newRight));
        } else {
          assert(after != bitPart[p].begin());
          --after;
          int left1 = after->first, right1 = i;
          int left2 = i + 1, right2 = after->second;
          res -= ((right2 - left1) * (right2 - left1 + 1LL) / 2) << p;
          bitPart[p].erase(after);
          if (left1 != right1) {
            res += ((right1 - left1) * (right1 - left1 + 1LL) / 2) << p;
            bitPart[p].insert(make_pair(left1, right1));
          }
          if (left2 != right2) {
            res += ((right2 - left2) * (right2 - left2 + 1LL) / 2) << p;
            bitPart[p].insert(make_pair(left2, right2));
          }
        }
      }
    a[i] = v;
    printf("%I64d\n", res);
  }
  return 0;
}