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 bfsz = 1 << 16;
char bf[bfsz + 5];
int rsz = 0;
int ptr = 0;
char gc() {
  if (rsz <= 0) {
    ptr = 0;
    rsz = fread(bf, 1, bfsz, stdin);
    if (rsz <= 0) return EOF;
  }
  --rsz;
  return bf[ptr++];
}
void ga(char &c) {
  c = EOF;
  while (!isalpha(c)) c = gc();
}
int gs(char s[]) {
  int l = 0;
  char c = gc();
  while (isspace(c)) c = gc();
  while (c != EOF && !isspace(c)) {
    s[l++] = c;
    c = gc();
  }
  s[l] = '\0';
  return l;
}
template <class T>
bool gi(T &v) {
  v = 0;
  char c = gc();
  while (c != EOF && c != '-' && !isdigit(c)) c = gc();
  if (c == EOF) return false;
  bool neg = c == '-';
  if (neg) c = gc();
  while (isdigit(c)) {
    v = v * 10 + c - '0';
    c = gc();
  }
  if (neg) v = -v;
  return true;
}
bool exitInput = false;
int ntest = 1, itest = 1;
const int dx[2] = {-1, 1};
const int dy[2] = {-1, 1};
const long long Mod = 1e9 + 7;
const int maxn = 1e5 + 5;
const int maxv = 18;
const int maxe = 1 + 5;
int n, m, a[maxv][maxn], R[maxv][maxn];
long long res;
void pre() {}
void read() {
  gi(n);
  gi(m);
  int i, j, k;
  for (i = 1; i <= n; ++i) {
    int x;
    gi(x);
    for (j = 0; j < maxv; ++j) {
      a[j][i] = x & 1;
      x >>= 1;
    }
  }
}
void solve() {
  int i, j, k;
  res = 0;
  for (i = 0; i < maxv; ++i) {
    R[i][n + 1] = 0;
    for (j = n; j >= 1; --j) {
      if (a[i][j] == 1)
        R[i][j] = R[i][j + 1] + 1;
      else
        R[i][j] = 0;
      if (a[i][j] == 1) {
        res = res + (1LL << i) * R[i][j];
      }
    }
  }
  while (m--) {
    int x, p;
    gi(p);
    gi(x);
    for (i = 0; i < maxv; ++i) {
      k = x & 1;
      x >>= 1;
      if (k == a[i][p]) continue;
      if (a[i][p] == 1 && k == 0) {
        res = res - (1LL << i) * R[i][p];
        R[i][p] = 0;
        a[i][p] = k;
        for (j = p - 1; j >= 1 && a[i][j] == 1; --j) {
          res = res - (1LL << i) * R[i][j];
          R[i][j] = R[i][j + 1] + 1;
          res = res + (1LL << i) * R[i][j];
        }
      } else {
        R[i][p] = R[i][p + 1] + 1;
        res = res + (1LL << i) * R[i][p];
        a[i][p] = k;
        for (j = p - 1; j >= 1 && a[i][j] == 1; --j) {
          res = res - (1LL << i) * R[i][j];
          R[i][j] = R[i][j + 1] + 1;
          res = res + (1LL << i) * R[i][j];
        }
      }
    }
    cout << res << endl;
  }
}
int main() {
  pre();
  for (itest = 1; itest <= ntest; ++itest) {
    read();
    if (exitInput) {
      break;
    }
    solve();
  }
  return 0;
}