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;
const int N = 1e5 + 7;
const int M = 18;
const int inf = 1e9 + 7;
const long long base = 51123987;
int le[M][N * 3], ri[M][N * 3];
long long b[M][N * 3];
int x[N];
int n, m;
int kq;
void update(int k, int i, int l, int r, int u) {
  if (l == u && r == u) {
    le[k][i] += kq;
    b[k][i] = le[k][i];
    ri[k][i] = le[k][i];
    return;
  }
  int g = (l + r) >> 1, next = i << 1;
  if (u <= g) update(k, next, l, g, u);
  if (u > g) update(k, next + 1, g + 1, r, u);
  le[k][i] = le[k][next];
  if (le[k][next] == g - l + 1) le[k][i] += le[k][next + 1];
  ri[k][i] = ri[k][next + 1];
  if (ri[k][next + 1] == r - g) ri[k][i] += ri[k][next];
  b[k][i] = b[k][next] + b[k][next + 1];
  b[k][i] += (long long)ri[k][next] * le[k][next + 1];
}
int main() {
  cin >> n >> m;
  for (int i = 1; i < n + 1; i++) {
    cin >> x[i];
    for (int j = 0; j < M; j++) {
      if (x[i] & (1 << j)) {
        kq = 1;
        update(j, 1, 1, n, i);
      }
    }
  }
  for (int test = 0; test < m; test++) {
    int u, v;
    scanf("%d%d", &u, &v);
    for (int j = 0; j < M; j++) {
      if (x[u] & (1 << j)) {
        kq = -1;
        update(j, 1, 1, n, u);
      }
    }
    long long res = 0;
    x[u] = v;
    for (int j = 0; j < M; j++) {
      if (x[u] & (1 << j)) {
        kq = 1;
        update(j, 1, 1, n, u);
      }
      res += (1 << j) * b[j][1];
    }
    cout << res << endl;
  }
}