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;
set<int> my_start[18], my_end[18];
set<int>::iterator my_it_left, my_it_right;
int n, m, f;
long long ans, l, r, p;
bool have[100002][18];
void add(int pos, int d, long long k) {
  have[pos][d] = true;
  p = pos;
  if (have[pos + 1][d] && have[pos - 1][d]) {
    my_it_left = --my_start[d].upper_bound(pos);
    l = *my_it_left;
    my_it_right = my_end[d].upper_bound(pos);
    r = *my_it_right;
    ans -= k * (p - l) * (p - l + 1) / 2 + k * (r - p) * (r - p + 1) / 2 -
           k * (r - l + 1) * (r - l + 2) / 2;
    my_end[d].erase(pos - 1);
    my_start[d].erase(pos + 1);
  } else if (have[pos + 1][d]) {
    my_it_right = my_end[d].lower_bound(pos);
    r = *my_it_right;
    ans -= k * (r - p) * (r - p + 1) / 2 - k * (r - p + 1) * (r - p + 2) / 2;
    my_start[d].insert(pos);
    my_start[d].erase(pos + 1);
  } else if (have[pos - 1][d]) {
    my_it_left = --my_start[d].lower_bound(pos);
    l = *my_it_left;
    ans -= k * (p - l) * (p - l + 1) / 2;
    ans += k * (p - l + 1) * (p - l + 2) / 2;
    my_end[d].insert(pos);
    my_end[d].erase(pos - 1);
  } else {
    my_start[d].insert(pos);
    my_end[d].insert(pos);
    ans += k;
  }
}
void remov(int pos, int d, long long k) {
  have[pos][d] = false;
  p = pos;
  if (have[pos + 1][d] && have[pos - 1][d]) {
    my_it_left = --my_start[d].upper_bound(pos);
    l = *my_it_left;
    my_it_right = my_end[d].upper_bound(pos);
    r = *my_it_right;
    ans += k * (p - l) * (p - l + 1) / 2 + k * (r - p) * (r - p + 1) / 2 -
           k * (r - l + 1) * (r - l + 2) / 2;
    my_end[d].insert(pos - 1);
    my_start[d].insert(pos + 1);
  } else if (have[pos + 1][d]) {
    my_it_right = my_end[d].lower_bound(pos);
    r = *my_it_right;
    ans += k * (r - p) * (r - p + 1) / 2 - k * (r - p + 1) * (r - p + 2) / 2;
    my_start[d].insert(pos + 1);
    my_start[d].erase(pos);
  } else if (have[pos - 1][d]) {
    my_it_left = --my_start[d].lower_bound(pos);
    l = *my_it_left;
    ans += k * (p - l) * (p - l + 1) / 2;
    ans -= k * (p - l + 1) * (p - l + 2) / 2;
    my_end[d].insert(pos - 1);
    my_end[d].erase(pos);
  } else {
    my_start[d].erase(pos);
    my_end[d].erase(pos);
    ans -= k;
  }
}
int main() {
  scanf("%d %d", &n, &m);
  int num;
  for (int i = 0; i < 18; i++) {
    my_start[i].insert(0);
    my_end[i].insert(0);
    my_start[i].insert(n + 1);
    my_end[i].insert(n + 1);
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", &num);
    int k = 1;
    int d = 0;
    while (k <= num) {
      have[i][d] = k & num;
      k <<= 1;
      d++;
    }
  }
  long long k = 1;
  for (int i = 0; i < 18; i++) {
    long long c = 0;
    for (int j = 1; j <= n; j++) {
      if (!have[j][i]) {
        if (c > 0) {
          ans += k * (c) * (c + 1) / 2;
          my_end[i].insert(j - 1);
          c = 0;
        }
      } else {
        if (c == 0) {
          my_start[i].insert(j);
        }
        c++;
      }
      if (j == n) {
        if (c > 0) my_end[i].insert(j);
        ans += k * (c) * (c + 1) / 2;
      }
    }
    k <<= 1;
  }
  for (int i = 0; i < m; i++) {
    int posit, x1;
    scanf("%d %d", &posit, &x1);
    int k = 1;
    int d = 0;
    while (k <= 150000) {
      if (k & x1) {
        if (!have[posit][d]) {
          add(posit, d, k);
        }
      } else {
        if (have[posit][d]) {
          remov(posit, d, k);
        }
      }
      k <<= 1;
      d++;
    }
    printf("%I64d\n", ans);
  }
  return 0;
}