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 <typename T>
inline bool upmin(T &x, T y) {
  return y < x ? x = y, 1 : 0;
}
template <typename T>
inline bool upmax(T &x, T y) {
  return x < y ? x = y, 1 : 0;
}
const long double eps = 1e-11;
const long double pi = acos(-1);
const long long oo = 1 << 30;
const long long loo = 1ll << 62;
const long long mods = 1e9 + 7;
const long long MAXN = 100005;
const long long INF = 0x3f3f3f3f;
inline long long read() {
  long long f = 1, x = 0;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 3) + (x << 1) + (c ^ 48);
    c = getchar();
  }
  return x * f;
}
long long L[MAXN << 2][18], R[MAXN << 2][18], s[MAXN << 2][18], a[MAXN],
    S[MAXN << 2];
long long get(long long x) { return x * (x + 1) / 2; }
void up(long long x, long long l, long long r, long long mid) {
  S[x] = 0;
  for (long long i = 0; i < 17; i++) {
    L[x][i] = L[x << 1][i], R[x][i] = R[x << 1 | 1][i];
    if (L[x << 1][i] == mid - l + 1) L[x][i] += L[x << 1 | 1][i];
    if (R[x << 1 | 1][i] == r - mid) R[x][i] += R[x << 1][i];
    s[x][i] = s[x << 1][i] + s[x << 1 | 1][i] +
              get(R[x << 1][i] + L[x << 1 | 1][i]) - get(R[x << 1][i]) -
              get(L[x << 1 | 1][i]);
    S[x] += s[x][i] * (1 << i);
  }
}
void build(long long x, long long l, long long r) {
  if (l == r) {
    S[x] = 0;
    for (long long i = 0; i < 17; i++)
      s[x][i] = L[x][i] = R[x][i] = (a[l] >> i) & 1, S[x] += s[x][i] * (1 << i);
    return;
  }
  long long mid = (l + r) >> 1;
  build(x << 1, l, mid);
  build(x << 1 | 1, mid + 1, r);
  up(x, l, r, mid);
}
void update(long long x, long long l, long long r, long long y, long long z) {
  if (l == r) {
    S[x] = 0;
    for (long long i = 0; i < 17; i++)
      s[x][i] = L[x][i] = R[x][i] = (z >> i) & 1, S[x] += s[x][i] * (1 << i);
    return;
  }
  long long mid = (l + r) >> 1;
  if (y <= mid)
    update(x << 1, l, mid, y, z);
  else
    update(x << 1 | 1, mid + 1, r, y, z);
  up(x, l, r, mid);
}
signed main() {
  long long n = read(), Case = read();
  for (long long i = 1; i <= n; i++) a[i] = read();
  build(1, 1, n);
  while (Case--) {
    long long x = read(), y = read();
    update(1, 1, n, x, y);
    printf("%lld\n", S[1]);
  }
  return 0;
}