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 N = (1e5 + 10);
long long a[N];
set<long long> st[20];
long long len[20][N];
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  long long n, m;
  cin >> n >> m;
  for (long long i = 1; i <= n; i++) cin >> a[i];
  long long up = 17, ans = 0;
  for (long long i = 0; i < up; i++) {
    st[i].insert(0);
    st[i].insert(n + 2);
    long long cnt = 0, res = 1 << i;
    for (long long j = 1; j <= n; j++) {
      if ((a[j] >> i) & 1)
        cnt++;
      else if (cnt) {
        st[i].insert(j - cnt);
        len[i][j - cnt] = cnt;
        ans += (cnt + 1) * (cnt) / 2 * res;
        cnt = 0;
      }
    }
    if (cnt) {
      st[i].insert(n + 1 - cnt);
      len[i][n + 1 - cnt] = cnt;
      ans += (cnt + 1) * (cnt) / 2 * res;
    }
  }
  while (m--) {
    long long p, v;
    cin >> p >> v;
    for (long long i = 0; i < up; i++) {
      long long res = (1 << i);
      long long last = (a[p] >> i) & 1, now = (v >> i) & 1;
      if (last == now) continue;
      if (now == 1) {
        auto it2 = st[i].lower_bound(p);
        auto tmp = it2;
        auto it1 = --tmp;
        long long p1 = *it1, p2 = *it2;
        if (p1 + len[i][p1] == p && p + 1 == p2) {
          ans -= (len[i][p1] + 1) * len[i][p1] / 2 * res;
          ans -= (len[i][p2] + 1) * len[i][p2] / 2 * res;
          len[i][p1] += 1 + len[i][p2];
          ans += (len[i][p1] + 1) * len[i][p1] / 2 * res;
          st[i].erase(it2);
          len[i][p2] = 0;
        } else if (p1 + len[i][p1] == p) {
          ans -= (len[i][p1] + 1) * len[i][p1] / 2 * res;
          len[i][p1]++;
          ans += (len[i][p1] + 1) * len[i][p1] / 2 * res;
        } else if (p + 1 == p2) {
          ans -= (len[i][p2] + 1) * len[i][p2] / 2 * res;
          st[i].insert(p);
          len[i][p] = 1 + len[i][p2];
          ans += (len[i][p] + 1) * len[i][p] / 2 * res;
          st[i].erase(it2);
          len[i][p2] = 0;
        } else {
          st[i].insert(p);
          len[i][p] = 1;
          ans += (len[i][p] + 1) * len[i][p] / 2 * res;
        }
      } else {
        auto it1 = st[i].upper_bound(p);
        it1--;
        long long p1 = *it1;
        if (p1 + len[i][p1] - 1 == p) {
          ans -= (len[i][p1] + 1) * len[i][p1] / 2 * res;
          len[i][p1]--;
          ans += (len[i][p1] + 1) * len[i][p1] / 2 * res;
          if (len[i][p1] == 0) st[i].erase(it1);
        } else if (p == p1) {
          ans -= (len[i][p1] + 1) * len[i][p1] / 2 * res;
          if (len[i][p1] > 1) {
            st[i].insert(p1 + 1);
            len[i][p1 + 1] = len[i][p1] - 1;
            ans += (len[i][p1 + 1] + 1) * len[i][p1 + 1] / 2 * res;
          }
          st[i].erase(it1);
          len[i][p1] = 0;
        } else if (p1 != 0) {
          ans -= (len[i][p1] + 1) * len[i][p1] / 2 * res;
          st[i].insert(p + 1);
          len[i][p + 1] = p1 + len[i][p1] - (p + 1);
          ans += (len[i][p + 1] + 1) * len[i][p + 1] / 2 * res;
          len[i][p1] = p - p1;
          ans += (len[i][p1] + 1) * len[i][p1] / 2 * res;
        }
      }
    }
    a[p] = v;
    cout << ans << "\n";
  }
  return 0;
}