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 LOG = 18;
int MUL = 1;
set<pair<int, int> > intervals[LOG];
long long ans[LOG], F[1 << 18];
long long np1C2(long long x) { return F[x]; }
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int N, M;
  cin >> N >> M;
  for (int i = 1; i < (1 << 18); i++) {
    F[i] = F[i - 1] + i;
  }
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  for (int bit = 0; bit < LOG; bit++) {
    int cur = 0;
    for (int i = 0; i < N; i++) {
      if (A[i] & (1 << bit)) {
        cur++;
      } else {
        if (cur != 0) {
          intervals[bit].insert({i - cur, i - 1});
          ans[bit] += np1C2(cur);
        }
        cur = 0;
      }
    }
    if (cur) {
      intervals[bit].insert({N - cur, N - 1});
      ans[bit] += np1C2(cur);
    }
  }
  int cnt = 0;
  while (M--) {
    int ind, val;
    cin >> ind >> val;
    ind--;
    val /= MUL;
    for (int bit = 0; bit < LOG; bit++) {
      if (val & (1 << bit)) {
        if (intervals[bit].empty()) {
          intervals[bit].insert({ind, ind});
          ans[bit]++;
          continue;
        }
        pair<int, int> I1 = {-1, -1}, I2 = {-1, -1};
        auto it = --intervals[bit].upper_bound({ind, 1e9});
        if (it != intervals[bit].end()) {
          I1 = *it;
          it++;
          if (it != intervals[bit].end()) {
            I2 = *it;
          }
        } else {
          it = intervals[bit].upper_bound({ind, 1e9});
          if (it != intervals[bit].end()) {
            I1 = *it;
          }
        }
        if (I2.first > ind + 1) {
          I2 = {-1, -1};
        }
        if (I1.first > ind + 1 || I1.second < ind - 1) {
          I1 = I2;
          I2 = {-1, -1};
        }
        if (I1 == make_pair(-1, -1)) {
          intervals[bit].insert({ind, ind});
          ans[bit]++;
          continue;
        }
        vector<pair<int, int> > to_rem, to_add;
        if (I2 != make_pair(-1, -1)) {
          to_rem.push_back(I1);
          to_rem.push_back(I2);
          to_add.push_back({I1.first, I2.second});
        } else {
          if (I1.first == ind + 1) {
            to_rem.push_back(I1);
            to_add.push_back({ind, I1.second});
          } else if (I1.second == ind - 1) {
            to_rem.push_back(I1);
            to_add.push_back({I1.first, ind});
          }
        }
        for (pair<int, int> u : to_rem) {
          ans[bit] -= np1C2(u.second - u.first + 1);
          intervals[bit].erase(u);
        }
        for (pair<int, int> u : to_add) {
          ans[bit] += np1C2(u.second - u.first + 1);
          intervals[bit].insert(u);
        }
      } else {
        if (intervals[bit].empty()) {
          continue;
        }
        auto it = --intervals[bit].upper_bound({ind, 1e9});
        if (it == intervals[bit].end()) {
          continue;
        }
        pair<int, int> I = *it;
        if (I.second < ind || I.first > ind) {
          continue;
        }
        vector<pair<int, int> > to_rem, to_add;
        to_rem.push_back(I);
        if (I.first <= ind - 1) {
          to_add.push_back({I.first, ind - 1});
        }
        if (ind + 1 <= I.second) {
          to_add.push_back({ind + 1, I.second});
        }
        for (pair<int, int> u : to_rem) {
          ans[bit] -= np1C2(u.second - u.first + 1);
          intervals[bit].erase(u);
        }
        for (pair<int, int> u : to_add) {
          ans[bit] += np1C2(u.second - u.first + 1);
          intervals[bit].insert(u);
        }
      }
    }
    long long ret = 0;
    for (int bit = 0; bit < LOG; bit++) {
      ret += (1LL << bit) * ans[bit];
    }
    cout << ret << '\n';
  }
  cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n";
  return 0;
}