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 MAX = 100000 + 10;
const int MAXK = 18;
int rec[MAX];
inline long long getans(long long x, int k) {
  return (x + 1) * x / 2 * (1LL << k);
}
struct stree {
  int L[MAX << 2], R[MAX << 2], num;
  void pull(int n, int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (L[(n << 1) + 1] == mid - l + 1)
      L[n] = L[(n << 1) + 1] + L[(n << 1) + 2];
    else
      L[n] = L[(n << 1) + 1];
    if (R[(n << 1) + 2] == r - mid)
      R[n] = R[(n << 1) + 2] + R[(n << 1) + 1];
    else
      R[n] = R[(n << 1) + 2];
  }
  void init(int n, int l, int r) {
    if (l == r) {
      L[n] = R[n] = ((rec[l] & (1 << num)) != 0);
      return;
    }
    int mid = (l + r) >> 1;
    init((n << 1) + 1, l, mid);
    init((n << 1) + 2, mid + 1, r);
    pull(n, l, r);
  }
  int queryl(int n, int l, int r, int ll, int rr) {
    if (rr < ll) return 0;
    if (l == ll && r == rr) return L[n];
    int mid = (l + r) >> 1;
    if (ll > mid) {
      return queryl((n << 1) + 2, mid + 1, r, ll, rr);
    } else if (rr <= mid) {
      return queryl((n << 1) + 1, l, mid, ll, rr);
    } else {
      int tl = queryl((n << 1) + 1, l, mid, ll, mid);
      if (tl != mid - ll + 1) return tl;
      int tr = queryl((n << 1) + 2, mid + 1, r, mid + 1, rr);
      return tl + tr;
    }
  }
  int queryr(int n, int l, int r, int ll, int rr) {
    if (rr < ll) return 0;
    if (l == ll && r == rr) return R[n];
    int mid = (l + r) >> 1;
    if (ll > mid) {
      return queryr((n << 1) + 2, mid + 1, r, ll, rr);
    } else if (rr <= mid) {
      return queryr((n << 1) + 1, l, mid, ll, rr);
    } else {
      int tr = queryr((n << 1) + 2, mid + 1, r, mid + 1, rr);
      if (tr != rr - mid) return tr;
      int tl = queryr((n << 1) + 1, l, mid, ll, mid);
      return tr + tl;
    }
  }
  void update(int n, int l, int r, int p) {
    if (l == r) {
      L[n] = R[n] = 1 - L[n];
      return;
    }
    int mid = (l + r) >> 1;
    if (p > mid)
      update((n << 1) + 2, mid + 1, r, p);
    else
      update((n << 1) + 1, l, mid, p);
    pull(n, l, r);
  }
} T[MAXK];
int main() {
  int n, m, x, y;
  long long ans = 0;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", &rec[i]);
  for (int k = 0; k < MAXK; k++) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
      if (rec[i] & (1 << k)) {
        cnt++;
      } else {
        ans += getans((long long)cnt, k);
        cnt = 0;
      }
    }
    ans += getans((long long)cnt, k);
  }
  for (int i = 0; i < MAXK; i++) {
    T[i].num = i;
    T[i].init(0, 0, n - 1);
  }
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &x, &y);
    x--;
    for (int k = 0; k < MAXK; k++) {
      if ((rec[x] & (1 << k)) != (y & (1 << k))) {
        int rcnt = T[k].queryl(0, 0, n - 1, x + 1, n - 1);
        int lcnt = T[k].queryr(0, 0, n - 1, 0, x - 1);
        if ((y & (1 << k)) == 0) {
          int tmp = lcnt + rcnt + 1;
          ans -= getans((long long)tmp, k);
          ans += getans((long long)lcnt, k);
          ans += getans((long long)rcnt, k);
        } else {
          int tmp = lcnt + rcnt + 1;
          ans += getans((long long)tmp, k);
          ans -= getans((long long)lcnt, k);
          ans -= getans((long long)rcnt, k);
        }
        T[k].update(0, 0, n - 1, x);
      }
    }
    rec[x] = y;
    printf("%I64d\n", ans);
  }
  return 0;
}