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 INF = 0x3f3f3f3f;
const double EPS = 1e-10;
const int MOD = 1000000007;
const int MAXN = 110000;
const double PI = acos(-1.0);
template <class T>
T abs(T x) {
  return x < 0 ? -x : x;
}
int num, kase;
int flag[22][MAXN];
long long fun() {
  long long ret = 0;
  for (int index = 0; index < (21); ++index) {
    long long cnt = 0, t = 0;
    for (int i = (1); i <= (num + 1); ++i) {
      if (flag[index][i] == 1)
        cnt++;
      else {
        t += ((cnt * cnt + cnt) >> 1);
        cnt = 0;
      }
    }
    ret += (1 << index) * t;
  }
  return ret;
}
void findlr(int* f, int n, int& l, int& r) {
  int i = n - 1;
  while (f[i] == 1) i--;
  l = i + 1;
  i = n + 1;
  while (f[i] == 1) i++;
  r = i - 1;
}
int main() {
  int t, p;
  while (~scanf("%d%d", &num, &kase)) {
    memset(flag, 0, sizeof(flag));
    for (int i = (1); i <= (num); ++i) {
      scanf("%d", &t);
      p = 1;
      for (int ind = 0; ind < (21); ++ind) {
        flag[ind][i] = ((t & p) > 0);
        p <<= 1;
      }
    }
    long long ans = fun();
    int a, b, l, r;
    for (int tt = 0; tt < (kase); ++tt) {
      scanf("%d%d", &a, &b);
      for (int ind = 0; ind < (21); ++ind) {
        p = 1 << ind;
        if (((b & p) > 0) != flag[ind][a]) {
          findlr(flag[ind], a, l, r);
          long long lenl = a - l, lenr = r - a;
          ans += (1 - flag[ind][a] * 2) * (1 << ind) *
                 (lenl * lenr + lenl + lenr + 1);
          flag[ind][a] = !flag[ind][a];
        }
      }
      cout << ans << endl;
    }
  }
  return 0;
}