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 n, m, number;
long long ans;
set<int> zeroes[18], ones[18];
set<int>::iterator my_it;
void fullfill(int number, int pos) {
  int k = 1;
  int d = -1;
  while (d < 19) {
    d++;
    if (d == 18) return;
    if (k & number) {
      ones[d].insert(pos);
    } else {
      zeroes[d].insert(pos);
    }
    k <<= 1;
  }
}
void refreshAns(int pos, int value) {
  long long k = 1;
  int d = -1;
  while (d < 19) {
    d++;
    if (d == 18) return;
    if (k & value) {
      my_it = ones[d].lower_bound(pos);
      if (*my_it != pos) {
        set<int>::iterator m_it = zeroes[d].lower_bound(pos);
        my_it = m_it;
        long long r = *++m_it;
        long long p = pos;
        long long l = *--my_it;
        ans += k * ((r - l - 1) * (r - l) - (p - l - 1) * (p - l) -
                    (r - p - 1) * (r - p));
        zeroes[d].erase(pos);
        ones[d].insert(pos);
      }
    } else {
      my_it = zeroes[d].lower_bound(pos);
      if (*my_it != pos) {
        long long p = pos;
        long long r = *my_it;
        long long l = *--my_it;
        ans -= k * ((r - l - 1) * (r - l) - (r - p - 1) * (r - p) -
                    (p - l - 1) * (p - l));
        ones[d].erase(pos);
        zeroes[d].insert(pos);
      }
    }
    k <<= 1;
  }
}
void getAns() {
  long long value = 1;
  for (int i = 0; i < 18; i++) {
    int posO = 0;
    int posZA = -1;
    int posZB = -1;
    while (1) {
      posO = *ones[i].lower_bound(posO);
      if (posO == n) {
        break;
      }
      my_it = zeroes[i].upper_bound(posO);
      posZA = *my_it;
      posZB = (*--my_it);
      long long l = posZA;
      long long r = posZB;
      ans += value * (l - r - 1) * (l - r);
      posO = *zeroes[i].lower_bound(posO);
    }
    value *= 2;
  }
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < 18; i++) {
    zeroes[i].insert(n);
    ones[i].insert(n);
    zeroes[i].insert(-1);
    ones[i].insert(-1);
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", &number);
    fullfill(number, i);
  }
  getAns();
  for (int i = 0; i < m; i++) {
    int pos, v;
    scanf("%d %d", &pos, &v);
    refreshAns(pos - 1, v);
    printf("%I64d\n", ans / 2);
  }
  return 0;
}