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 = 1 << 17;
const int Z = 17;
long long t[100000][Z];
long long st[2 * N][Z];
void addValue(long long t, long long a, long long v) {
  a += N;
  for (; a; a /= 2) st[a][t] += v;
}
long long getSum(long long t, long long a, long long b) {
  a += N;
  b += N;
  long long sum = 0;
  for (; a <= b; a /= 2, b /= 2) {
    if (a & 1) sum += st[a++][t];
    if (~b & 1) sum += st[b--][t];
  }
  return sum;
}
int main() {
  ios_base::sync_with_stdio(0);
  long long n, m;
  cin >> n >> m;
  for (long long i = 0; i < n; ++i) {
    long long q;
    cin >> q;
    for (long long j = 0; j < Z; q /= 2, ++j) {
      long long y = q & 1;
      st[i + N][j] = y;
    }
  }
  for (long long i = 0; i < Z; ++i) {
    for (long long j = N - 1; j; --j) {
      st[j][i] = st[j * 2][i] + st[j * 2 + 1][i];
    }
  }
  long long sum = 0;
  for (long long q = 0; q < Z; ++q) {
    for (long long i = 0; i < n; ++i) {
      if (st[i + N][q] == 1) {
        long long lo = i;
        long long hi = N - 1;
        long long best = 0;
        for (; lo <= hi;) {
          long long mid = (lo + hi) >> 1;
          if (getSum(q, i, mid) >= mid - i + 1) {
            lo = mid + 1;
            best = max(best, mid);
          } else
            hi = mid - 1;
        }
        sum += ((best - i + 1) * (best - i + 2) / 2) * (1ll << q);
        i = best;
      }
    }
  }
  for (long long i = 0; i < m; ++i) {
    long long p, v;
    cin >> p >> v;
    --p;
    for (long long q = 0; q < Z; ++q, v /= 2) {
      if ((v & 1) != st[p + N][q]) {
        if ((v & 1) == 1) {
          addValue(q, p, 1);
        }
        long long lo = p;
        long long hi = N - 1;
        long long bestHi = 0;
        for (; lo <= hi;) {
          long long mid = (lo + hi) >> 1;
          if (getSum(q, p, mid) >= mid - p + 1) {
            lo = mid + 1;
            bestHi = max(bestHi, mid);
          } else
            hi = mid - 1;
        }
        lo = 0;
        hi = p;
        long long bestLo = 1e15;
        for (; lo <= hi;) {
          long long mid = (lo + hi) >> 1;
          if (getSum(q, mid, p) >= p - mid + 1) {
            hi = mid - 1;
            bestLo = min(bestLo, mid);
          } else
            lo = mid + 1;
        }
        if (v & 1) {
          sum -= ((p - bestLo) * (p - bestLo + 1) / 2) * (1ll << q);
          sum -= ((bestHi - p) * (bestHi - p + 1) / 2) * (1ll << q);
          sum +=
              ((bestHi - bestLo + 1) * (bestHi - bestLo + 2) / 2) * (1ll << q);
        } else {
          addValue(q, p, -1);
          sum += ((p - bestLo) * (p - bestLo + 1) / 2) * (1ll << q);
          sum += ((bestHi - p) * (bestHi - p + 1) / 2) * (1ll << q);
          sum -=
              ((bestHi - bestLo + 1) * (bestHi - bestLo + 2) / 2) * (1ll << q);
        }
      }
    }
    cout << sum << '\n';
  }
}