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;
int main() {
  cin.sync_with_stdio(0);
  int N, M;
  cin >> N >> M;
  vector<int> A[20];
  for (int i = 0; i < 20; i++) A[i].resize(N);
  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    for (int j = 0; j < 20; j++) {
      A[j][i] = (int)(a % 2 != 0);
      a /= 2;
    }
  }
  map<int, int> X[20];
  long long ans = 0;
  for (int i = 0; i < 20; i++) {
    int x = -1;
    for (int j = 0; j < N; j++) {
      if (x == -1 && A[i][j]) x = j;
      if (x != -1 && !A[i][j]) {
        X[i][j - 1] = x;
        x = -1;
      }
    }
    if (x != -1) X[i][N - 1] = x;
    for (auto it = X[i].begin(); it != X[i].end(); it++)
      ans += (1 << i) * 1LL * (it->first - it->second + 1) * 1LL *
             (it->first - it->second + 2) / 2;
  }
  for (int i = 0; i < M; i++) {
    int p, v;
    cin >> p >> v;
    p--;
    for (int j = 0; j < 20; j++) {
      if ((int)(v % 2 != 0) == A[j][p]) {
        v /= 2;
        continue;
      }
      if (v % 2 != 0) {
        auto x = X[j].lower_bound(p);
        A[j][p] = 1;
        int a = p, b = p;
        if (x != X[j].begin()) {
          auto y = x;
          y--;
          if (y->first == p - 1) {
            b = y->second;
            ans -= (1 << j) * 1LL * (y->first - y->second + 2) * 1LL *
                   (y->first - y->second + 1) / 2;
            X[j].erase(y);
          }
        }
        if (x != X[j].end())
          if (x->second == p + 1) {
            ans -= (1 << j) * 1LL * (x->first - x->second + 2) * 1LL *
                   (x->first - x->second + 1) / 2;
            a = x->first;
            X[j].erase(x);
          }
        ans += (1 << j) * 1LL * (a - b + 1) * 1LL * (a - b + 2) / 2;
        X[j][a] = b;
        v /= 2;
        continue;
      }
      A[j][p] = 0;
      auto x = X[j].lower_bound(p);
      ans -= (1 << j) * 1LL * (x->first - x->second + 1) * 1LL *
             (x->first - x->second + 2) / 2;
      ans += (1 << j) * 1LL * (x->first - p) * 1LL * (x->first - p + 1) / 2;
      ans += (1 << j) * 1LL * (p - x->second) * 1LL * (p - x->second + 1) / 2;
      if (x->second != p) X[j][p - 1] = x->second;
      if (x->first != p)
        X[j][x->first] = p + 1;
      else
        X[j].erase(x);
      v /= 2;
    }
    cout << ans << "\n";
  }
  return 0;
}