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 long long inf = 2e9, mod = 1e9 + 7;
const long long N = 1 * 1e5 + 1, N2 = 5000 + 3, LOGN = 16 + 1;
struct BITlazy {
  long long n;
  vector<long long> BIT1, BIT2;
  BITlazy() {}
  BITlazy(long long _n) {
    n = _n;
    BIT1.assign(n + 1, 0);
    BIT2.assign(n + 1, 0);
  }
  void add(vector<long long>& b, long long ind, long long x) {
    while (ind <= n) {
      b[ind] += x;
      ind += ind & (-ind);
    }
  }
  void rangeAdd(long long l, long long r, long long val) {
    add(BIT1, l, val);
    add(BIT1, r + 1, -val);
    add(BIT2, l, val * (l - 1));
    add(BIT2, r + 1, -val * r);
  }
  long long sum(vector<long long>& b, long long ind) {
    long long sum = 0;
    while (ind > 0) {
      sum += b[ind];
      ind -= ind & (-ind);
    }
    return sum;
  }
  long long prefixSum(long long ind) {
    return sum(BIT1, ind) * ind - sum(BIT2, ind);
  }
  long long rangeSum(long long l, long long r) {
    return prefixSum(r) - prefixSum(l - 1);
  }
};
long long a[N];
set<long long> zero[LOGN];
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n, m;
  cin >> n >> m;
  for (long long i = 1; i <= n; ++i) cin >> a[i];
  vector<BITlazy> occ(LOGN, BITlazy(n));
  for (long long j = 0; j < LOGN; ++j) {
    long long bitOcc = 0;
    for (long long i = n; i >= 1; --i) {
      if (a[i] & (1 << j))
        ++bitOcc, occ[j].rangeAdd(i, i, bitOcc);
      else
        bitOcc = 0, zero[j].insert(i);
    }
    zero[j].insert({0, n + 1});
  }
  while (m--) {
    long long i, x;
    cin >> i >> x;
    for (long long j = 0; j < LOGN; ++j)
      if ((x & (1 << j)) != (a[i] & (1 << j))) {
        auto it1 = prev(zero[j].lower_bound(i));
        long long nbL = i - 1 - *it1;
        auto it2 = zero[j].upper_bound(i);
        long long nbR = *it2 - 1 - i;
        bool has = (a[i] & (1 << j));
        long long curBitOcc = (has ? 1 + nbR : 0);
        long long newBitOcc = (has ? 0 : 1 + nbR);
        long long diff = newBitOcc - curBitOcc;
        occ[j].rangeAdd(i - nbL, i, diff);
        if (diff) {
          if (!newBitOcc) zero[j].insert(i);
          if (!curBitOcc) zero[j].erase(i);
        }
      }
    a[i] = x;
    long long sum = 0;
    for (long long j = 0; j < LOGN; ++j)
      sum += (long long)(1 << j) * occ[j].rangeSum(1, n);
    cout << sum << '\n';
  }
  return 0;
}