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;
template <class T>
inline T bigmod(T p, T e, T M) {
  long long ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  }
  return (T)ret;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T modinverse(T a, T M) {
  return bigmod(a, M - 2, M);
}
long long ar[22][100001], sum[22];
long long seg[22][400001];
void insert(int ii, int idx, int s, int e, int p, int v) {
  if (s == e) {
    seg[ii][idx] = v;
    return;
  }
  int mid = (s + e) / 2;
  if (p <= mid)
    insert(ii, idx * 2 + 1, s, mid, p, v);
  else
    insert(ii, idx * 2 + 2, mid + 1, e, p, v);
  seg[ii][idx] = seg[ii][idx * 2 + 1] + seg[ii][idx * 2 + 2];
}
int QL(int ii, int idx, int s, int e, int st, int ed) {
  if (ed < st || seg[ii][idx] == 0) return 1000000;
  if (s == e) return s;
  int mid = (s + e) / 2;
  if (ed <= mid)
    return QL(ii, idx * 2 + 1, s, mid, st, ed);
  else if (st > mid)
    return QL(ii, idx * 2 + 2, mid + 1, e, st, ed);
  else {
    int a = QL(ii, idx * 2 + 1, s, mid, st, mid);
    if (a < 1000000) return a;
    return QL(ii, idx * 2 + 2, mid + 1, e, mid + 1, ed);
  }
}
int QR(int ii, int idx, int s, int e, int st, int ed) {
  if (ed < st || seg[ii][idx] == 0) return -1;
  if (s == e) return s;
  int mid = (s + e) / 2;
  if (ed <= mid)
    return QR(ii, idx * 2 + 1, s, mid, st, ed);
  else if (st > mid)
    return QR(ii, idx * 2 + 2, mid + 1, e, st, ed);
  else {
    int a = QR(ii, idx * 2 + 2, mid + 1, e, mid + 1, ed);
    if (a >= 0) return a;
    return QR(ii, idx * 2 + 1, s, mid, st, mid);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long a, b, c, d, e, f = 0, g, h = 0, x, y, z;
  cin >> a >> b;
  for (int i = (0); i < (a); ++i) {
    cin >> d;
    for (int j = (0); j < (20); ++j) {
      ar[j][i] = d % 2;
      d /= 2;
    }
  }
  for (int i = 0; i < 20; i++) {
    c = 0;
    for (int j = 0; j < a; j++) {
      if (ar[i][j] == 0) {
        sum[i] += c * (c + 1ll) / 2ll;
        c = 0;
        insert(i, 0, 0, a - 1, j, 1);
      } else
        c++;
    }
    sum[i] += c * (c + 1ll) / 2ll;
  }
  for (int i = (0); i < (b); ++i) {
    cin >> c >> d;
    c--;
    h = 0;
    for (int j = (0); j < (20); ++j) {
      e = d % 2;
      d /= 2;
      if (ar[j][c] == e) {
        h += sum[j] * (1ll << j);
        continue;
      }
      if (ar[j][c] == 0) {
        x = QR(j, 0, 0, a - 1, 0, c - 1);
        y = QL(j, 0, 0, a - 1, c + 1, a - 1);
        y = min(y, a);
        f = (c - x) * (c - x - 1ll) / 2ll;
        f += (y - c) * (y - c - 1ll) / 2ll;
        sum[j] -= f;
        f = (y - x - 1);
        sum[j] += f * (f + 1ll) / 2;
        insert(j, 0, 0, a - 1, c, 0);
      } else {
        x = QR(j, 0, 0, a - 1, 0, c - 1);
        y = QL(j, 0, 0, a - 1, c + 1, a - 1);
        y = min(y, a);
        x++;
        y--;
        f = (y - x + 1);
        sum[j] -= f * (f + 1) / 2ll;
        f = (c - x) * (c - x + 1ll) / 2ll;
        f += (y - c) * (y - c + 1ll) / 2ll;
        sum[j] += f;
        insert(j, 0, 0, a - 1, c, 1);
      }
      ar[j][c] = e;
      h += sum[j] * (1ll << j);
    }
    cout << h << endl;
  }
}