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;
void desperate_optimization(int precision) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout.setf(ios::fixed);
  cout.setf(ios::showpoint);
  cout.precision(precision);
}
const int N = 1e5;
long long arr[N + 5];
long long ST[4 * N + 5];
void build(int idx, int l, int r) {
  if (l == r) {
    ST[idx] = arr[l];
    return;
  }
  int mid = (l + r) / 2;
  build(2 * idx, l, mid), build(2 * idx + 1, mid + 1, r);
  ST[idx] = (ST[2 * idx] & ST[2 * idx + 1]);
}
bool error = false;
long long sums, lsums;
void update(int idx, int l, int r, int tar, int v) {
  if (l == r) {
    ST[idx] = v;
    arr[l] = v;
    return;
  }
  int mid = (l + r) / 2;
  if (tar <= mid)
    update(2 * idx, l, mid, tar, v);
  else
    update(2 * idx + 1, mid + 1, r, tar, v);
  ST[idx] = (ST[2 * idx] & ST[2 * idx + 1]);
}
void queryright(int idx, int l, int r, int le, int ri, int x) {
  if (ri < le) return;
  if (r < le || ri < l) return;
  if (l == r) {
    sums += ((ST[idx] & x) ? 1 : 0);
    if ((ST[idx] & x) == 0) error = true;
    return;
  }
  if (le <= l && r <= ri) {
    if (ST[idx] & x) {
      sums += (r - l + 1);
      return;
    } else {
      error = true;
      int mid = (l + r) / 2;
      if (ST[2 * idx] & x) {
        sums += (mid - l + 1);
        queryright(2 * idx + 1, mid + 1, r, le, ri, x);
      } else {
        queryright(2 * idx, l, mid, le, ri, x);
      }
      return;
    }
  }
  int mid = (l + r) / 2;
  queryright(2 * idx, l, mid, le, ri, x);
  if (error == false) queryright(2 * idx + 1, mid + 1, r, le, ri, x);
}
void queryleft(int idx, int l, int r, int le, int ri, int x) {
  if (ri < le) return;
  if (r < le || ri < l) return;
  if (l == r) {
    lsums += ((ST[idx] & x) ? 1 : 0);
    if ((ST[idx] & x) == 0) error = true;
    return;
  }
  if (le <= l && r <= ri) {
    if (ST[idx] & x) {
      lsums += (r - l + 1);
      return;
    } else {
      error = true;
      int mid = (l + r) / 2;
      if (ST[2 * idx + 1] & x) {
        lsums += (r - mid);
        queryleft(2 * idx, l, mid, le, ri, x);
      } else {
        queryleft(2 * idx + 1, mid + 1, r, le, ri, x);
      }
      return;
    }
  }
  int mid = (l + r) / 2;
  queryleft(2 * idx + 1, mid + 1, r, le, ri, x);
  if (error == false) queryleft(2 * idx, l, mid, le, ri, x);
}
void hora(int tc) {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> arr[i];
  build(1, 1, n);
  long long res = 0;
  for (int i = 1; i <= n; i++) {
    for (long long j = 1; j <= N; j *= 2) {
      if ((arr[i] & j) == 0) continue;
      error = false;
      sums = 0;
      queryright(1, 1, n, i, n, j);
      res += sums * j;
    }
  }
  for (int i = 1; i <= m; i++) {
    int p, v;
    cin >> p >> v;
    long long tmp = arr[p];
    for (long long j = 1; j <= N; j *= 2) {
      if ((j & tmp) == (j & v)) continue;
      sums = 0;
      error = false;
      queryright(1, 1, n, p + 1, n, j);
      lsums = 0;
      error = false;
      queryleft(1, 1, n, 1, p - 1, j);
      lsums++;
      sums++;
      if (j & tmp) {
        res -= lsums * sums * j;
      } else {
        res += lsums * sums * j;
      }
    }
    update(1, 1, n, p, v);
    cout << res << '\n';
  }
}
int main() {
  desperate_optimization(10);
  int ntc = 1;
  for (int tc = 1; tc <= ntc; tc++) hora(tc);
  return 0;
}