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 double eps = 1e-10;
const double PI = atan(1.0) * 4;
const int inf = 2147483647 / 2;
const int maxn = 100006;
template <class T>
void checkmin(T &t, T x) {
  if (x < t) t = x;
}
template <class T>
void checkmax(T &t, T x) {
  if (x > t) t = x;
}
int ansl, ansr;
int an[maxn], num[20][maxn];
int lsum[20][maxn << 2], rsum[20][maxn << 2], msum[20][maxn << 2];
void pushup(int idx, int rt, int l, int r) {
  int ls = rt << 1, rs = ls | 1, m = (l + r) >> 1;
  lsum[idx][rt] = lsum[idx][ls];
  rsum[idx][rt] = rsum[idx][rs];
  if (lsum[idx][ls] == m - l + 1) lsum[idx][rt] += lsum[idx][rs];
  if (rsum[idx][rs] == r - m) rsum[idx][rt] += rsum[idx][ls];
  msum[idx][rt] =
      max(max(msum[idx][ls], msum[idx][rs]), rsum[idx][ls] + lsum[idx][rs]);
}
void build(int rt, int l, int r) {
  if (l == r) {
    int tmp, idx = 0;
    scanf("%d", &tmp);
    while (tmp) {
      int t = tmp & 1;
      num[idx][l] = t;
      lsum[idx][rt] = rsum[idx][rt] = msum[idx][rt] = t;
      ++idx;
      tmp >>= 1;
    }
    return;
  }
  int m = (l + r) >> 1;
  build(rt << 1, l, m);
  build(rt << 1 | 1, m + 1, r);
  for (long long i = (0); i <= (long long)(19); i++) pushup(i, rt, l, r);
}
void update(int t1, int idx, int v, int rt, int l, int r) {
  if (l == r) {
    lsum[idx][rt] = rsum[idx][rt] = msum[idx][rt] = v;
    num[idx][l] = v;
    return;
  }
  int m = (l + r) >> 1;
  if (t1 <= m) update(t1, idx, v, rt << 1, l, m);
  if (t1 > m) update(t1, idx, v, rt << 1 | 1, m + 1, r);
  pushup(idx, rt, l, r);
}
void query(int t1, int idx, int rt, int l, int r) {
  if (msum[idx][rt] == r - l + 1) {
    checkmin(ansl, l);
    checkmax(ansr, r);
    return;
  }
  if (l == r) return;
  int m = (l + r) >> 1;
  if (m - rsum[idx][rt << 1] + 1 <= t1 && t1 <= m + lsum[idx][rt << 1 | 1])
    checkmin(ansl, m - rsum[idx][rt << 1] + 1),
        checkmax(ansr, m + lsum[idx][rt << 1 | 1]);
  if (t1 <= m)
    query(t1, idx, rt << 1, l, m);
  else
    query(t1, idx, rt << 1 | 1, m + 1, r);
}
int main() {
  int n, m;
  while (scanf("%d%d", &n, &m) != EOF) {
    memset(num, 0, sizeof(num));
    memset(lsum, 0, sizeof(lsum));
    memset(rsum, 0, sizeof(rsum));
    memset(msum, 0, sizeof(msum));
    long long ans = 0;
    build(1, 1, n);
    for (long long i = (0); i <= (long long)(19); i++) {
      long long t = 0;
      for (long long j = (0); j <= (long long)(n); j++) {
        if (num[i][j])
          ++t;
        else
          ans += (1LL << (i)) * (t + 1) * t / 2, t = 0;
      }
      if (t) ans += (1LL << (i)) * (t + 1) * t / 2;
    }
    int t1, t2;
    while (m--) {
      scanf("%d%d", &t1, &t2);
      int tmp = t2, idx = 0;
      while (tmp) {
        int c = tmp & 1, tc = num[idx][t1];
        if (c != tc) {
          ansl = n + 1;
          ansr = 0;
          if (c == 1) {
            update(t1, idx, c, 1, 1, n);
            query(t1, idx, 1, 1, n);
            ans += (1LL << (idx)) *
                   (1 + ansr - ansl + (long long)(ansr - t1) * (t1 - ansl));
          } else {
            query(t1, idx, 1, 1, n);
            ans -= (1LL << (idx)) *
                   (1 + ansr - ansl + (long long)(ansr - t1) * (t1 - ansl));
            update(t1, idx, c, 1, 1, n);
          }
        }
        ++idx;
        tmp >>= 1;
      }
      for (long long i = (idx); i <= (long long)(19); i++)
        if (num[i][t1]) {
          ansl = n + 1;
          ansr = 0;
          query(t1, i, 1, 1, n);
          ans -= (1LL << (i)) *
                 (1 + ansr - ansl + (long long)(ansr - t1) * (t1 - ansl));
          update(t1, i, 0, 1, 1, n);
        }
      printf("%I64d\n", ans);
    }
  }
  return 0;
}