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 maxn = 1e5;
const int maxl = 20;
int n, segp[maxl][4 * maxn], segs[maxl][4 * maxn];
long long int sega[maxl][4 * maxn];
long long int f(int n) { return ((1LL * n * (n + 1)) >> 1LL); }
void add(int idx, int val, int bin, int L = 0, int R = n, int id = 1) {
  if (L == R - 1) {
    sega[bin][id] = segs[bin][id] = segp[bin][id] = val;
    return;
  }
  int mid = (L + R) >> 1;
  if (idx < mid)
    add(idx, val, bin, L, mid, id * 2 + 0);
  else
    add(idx, val, bin, mid, R, id * 2 + 1);
  segp[bin][id] =
      (segp[bin][id * 2 + 0] == mid - L ? segp[bin][id * 2 + 1] : 0) +
      segp[bin][id * 2 + 0];
  segs[bin][id] =
      (segs[bin][id * 2 + 1] == R - mid ? segs[bin][id * 2 + 0] : 0) +
      segs[bin][id * 2 + 1];
  sega[bin][id] = sega[bin][id * 2 + 0] + sega[bin][id * 2 + 1];
  sega[bin][id] -= f(segs[bin][id * 2 + 0]) + f(segp[bin][id * 2 + 1]);
  sega[bin][id] += f(segs[bin][id * 2 + 0] + segp[bin][id * 2 + 1]);
}
void _add(int idx, int val) {
  for (int i = 0; i < maxl; i++) add(idx, val % 2, i), val /= 2;
}
long long int get() {
  long long int ret = 0;
  for (int i = 0; i < maxl; i++) ret += 1LL * (1LL << i) * sega[i][1];
  return ret;
}
int main() {
  ios_base::sync_with_stdio(false);
  int m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    int val;
    cin >> val;
    _add(i, val);
  }
  while (m--) {
    int idx, val;
    cin >> idx >> val;
    idx--;
    _add(idx, val);
    cout << get() << '\n';
  }
  return 0;
}