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;
void update(set<pair<int, int> > arr[], const int& p, const int& v,
            long long& sum) {
  pair<int, int> tempPair = make_pair(p, p);
  long long twoPower = 1;
  for (int i = 0; i < 20; ++i, twoPower *= 2) {
    set<pair<int, int> >::iterator it[2], targetIt = arr[i].end();
    it[0] = arr[i].lower_bound(tempPair), it[1] = arr[i].upper_bound(tempPair);
    if (it[1] != arr[i].begin()) --it[1];
    for (int j = 0; j < 2; ++j)
      if (it[j] != arr[i].end() && p >= it[j]->first && p <= it[j]->second)
        targetIt = it[j];
    if (v & (1 << i)) {
      if (targetIt == arr[i].end()) {
        sum += twoPower;
        auto itInserted = arr[i].insert(tempPair).first;
        for (int j = 0; j < 2 && itInserted != arr[i].end();
             ++j, ++itInserted) {
          if (itInserted == arr[i].begin()) continue;
          auto tempIt = itInserted;
          --tempIt;
          if (itInserted->first - tempIt->second == 1) {
            long long n = itInserted->second - itInserted->first + 1;
            sum -= twoPower * n * (n + 1) / 2;
            n = tempIt->second - tempIt->first + 1;
            sum -= twoPower * n * (n + 1) / 2;
            auto tempIt2 =
                arr[i]
                    .insert(make_pair(tempIt->first, itInserted->second))
                    .first;
            arr[i].erase(tempIt), arr[i].erase(itInserted);
            itInserted = tempIt2;
            n = itInserted->second - itInserted->first + 1;
            sum += twoPower * n * (n + 1) / 2;
          }
        }
      }
    } else {
      if (targetIt == arr[i].end()) continue;
      long long n = targetIt->second - targetIt->first + 1;
      sum -= twoPower * n * (n + 1) / 2;
      int begin1 = targetIt->first, end1 = p - 1;
      int begin2 = p + 1, end2 = targetIt->second;
      n = end1 - begin1 + 1, sum += twoPower * n * (n + 1) / 2;
      n = end2 - begin2 + 1, sum += twoPower * n * (n + 1) / 2;
      arr[i].erase(targetIt);
      if (begin1 <= end1) arr[i].insert(make_pair(begin1, end1));
      if (begin2 <= end2) arr[i].insert(make_pair(begin2, end2));
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  set<pair<int, int> > arr[20];
  int tempArr[100001];
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; ++i) cin >> tempArr[i];
  tempArr[n++] = 0;
  long long sum = 0;
  long long twoPower = 1;
  for (int i = 0; i < 20; ++i, twoPower *= 2) {
    int lastJ = 0;
    while (lastJ < n) {
      if ((tempArr[lastJ] & (1 << i)) == 0) {
        ++lastJ;
        continue;
      }
      int tempJ = lastJ;
      while (((tempArr[tempJ] & (1 << i)) != 0)) ++tempJ;
      arr[i].insert(make_pair(lastJ, tempJ - 1));
      long long nCtr = tempJ - lastJ;
      sum += twoPower * nCtr * (nCtr + 1) / 2;
      lastJ = tempJ;
    }
  }
  int p, v;
  for (int i = 0; i < m; ++i) {
    cin >> p >> v;
    --p;
    update(arr, p, v, sum);
    cout << sum << "\n";
  }
  return 0;
}