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;
long long bits[100500][20], a[100500], i, j, n, m, x, l, y, b[100500][20], rez;
set<long long> pairs[20];
int main() {
  cin >> n >> m;
  for (i = 0; i < n; i++) cin >> a[i];
  for (i = 0; i < n; i++)
    for (j = 0; j < 17; j++)
      if (a[i] & (1 << j)) {
        bits[i][j] = 1;
      }
  for (j = 0; j < 17; j++) {
    i = 0;
    while (i < n) {
      while (bits[i][j] == 0 && i < n) {
        i++;
      }
      pairs[j].insert(i);
      x = i;
      while (bits[i][j] == 1 && i < n) i++;
      b[x][j] = i - x;
      rez += (((i - x) * (i - x + 1)) / 2) * (1 << j);
    }
  }
  for (i = 0; i < m; i++) {
    cin >> x >> y;
    x--;
    for (j = 0; j < 17; j++) {
      long long tmp = (y & (1 << j));
      if (tmp > 0) tmp = 1;
      if (tmp == bits[x][j]) continue;
      if (tmp == 1) {
        if ((bits[x - 1][j] == 0 || x == 0) &&
            (bits[x + 1][j] == 0 || x == n - 1)) {
          b[x][j] = 1;
          pairs[j].insert(x);
          rez += (1 << j);
        }
        if ((bits[x - 1][j] == 0 || x == 0) &&
            (bits[x + 1][j] == 1 && x < n - 1)) {
          b[x][j] = b[x + 1][j] + 1;
          b[x + 1][j] = 0;
          pairs[j].erase(x + 1);
          pairs[j].insert(x);
          rez += (1 << j) * b[x][j];
        }
        if ((bits[x - 1][j] == 1 && x > 0) &&
            (bits[x + 1][j] == 0 || x == n - 1)) {
          set<long long>::iterator itr = pairs[j].lower_bound(x);
          itr--;
          l = *(itr);
          b[l][j]++;
          rez += (1 << j) * b[l][j];
        }
        if ((bits[x - 1][j] == 1 && x > 0) &&
            (bits[x + 1][j] == 1 && x < n - 1)) {
          set<long long>::iterator itr = pairs[j].lower_bound(x);
          itr--;
          l = *(itr);
          long long k1 = b[l][j];
          long long k2 = b[x + 1][j];
          b[l][j] = k1 + k2 + 1;
          pairs[j].erase(x + 1);
          b[x + 1][j] = 0;
          rez += (1 << j) * (((k1 + k2 + 1) * (k1 + k2 + 2)) / 2 -
                             (k1 * (k1 + 1)) / 2 - (k2 * (k2 + 1)) / 2);
        }
        bits[x][j] = 1;
      } else {
        if ((bits[x - 1][j] == 0 || x == 0) &&
            (bits[x + 1][j] == 0 || x == n - 1)) {
          b[x][j] = 0;
          pairs[j].erase(x);
          rez -= (1 << j);
        }
        if ((bits[x - 1][j] == 0 || x == 0) &&
            (bits[x + 1][j] == 1 && x < n - 1)) {
          b[x + 1][j] = b[x][j] - 1;
          rez -= (1 << j) * b[x][j];
          b[x][j] = 0;
          pairs[j].erase(x);
          pairs[j].insert(x + 1);
        }
        if ((bits[x - 1][j] == 1 && x > 0) &&
            (bits[x + 1][j] == 0 || x == n - 1)) {
          set<long long>::iterator itr = pairs[j].lower_bound(x);
          itr--;
          l = *(itr);
          rez -= (1 << j) * b[l][j];
          b[l][j]--;
        }
        if ((bits[x - 1][j] == 1 && x > 0) &&
            (bits[x + 1][j] == 1 && x < n - 1)) {
          set<long long>::iterator itr = pairs[j].lower_bound(x);
          itr--;
          l = *(itr);
          long long k1 = b[l][j] - (x - l + 1);
          long long k2 = x - l;
          b[l][j] = k2;
          b[x + 1][j] = k1;
          pairs[j].insert(x + 1);
          rez -= (1 << j) * (((k1 + k2 + 1) * (k1 + k2 + 2)) / 2 -
                             (k1 * (k1 + 1)) / 2 - (k2 * (k2 + 1)) / 2);
        }
        bits[x][j] = 0;
      }
    }
    cout << rez << endl;
  }
  return 0;
}