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;
set<pair<long long, long long> > s[17];
long long a[100002];
long long g[100002];
signed main() {
  ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  long long n, m;
  cin >> n >> m;
  for (long long i = 0; i <= n; i++) g[i] = (i * (i + 1)) / 2LL;
  long long ans = 0;
  for (long long i = 0; i <= n - 1; i++) cin >> a[i];
  for (long long j = 0; j <= 16; j++) {
    for (long long i = 0; i <= n - 1; i++) {
      if (a[i] & (1LL << j)) {
        long long len = 1;
        long long st = i;
        i++;
        while (1) {
          if (i == n or !(a[i] & (1LL << j))) {
            s[j].insert({st, len});
            ans += (g[len] * (1LL << j));
            break;
          }
          len++;
          i++;
        }
      }
    }
  }
  while (m--) {
    long long idx, val, pval;
    cin >> idx >> val;
    idx--;
    pval = a[idx];
    for (long long j = 0; j <= 16; j++) {
      if (val & (1LL << j) and !(pval & (1LL << j))) {
        auto it = s[j].lower_bound({idx, 1e9});
        if (it == s[j].end() or (*it).first != idx + 1)
          s[j].insert({idx, 1}), ans += (1LL << j);
        else
          ans += (1LL << j) * ((*it).second + 1),
              s[j].insert({idx, (*it).second + 1}), s[j].erase(it);
        it = s[j].lower_bound({idx, -1});
        if (it != s[j].begin()) {
          auto pt = prev(it);
          if ((*pt).second + (*pt).first - 1 == idx - 1) {
            ans -= (1LL << j) * (g[(*pt).second] + g[(*it).second]),
                ans += (1LL << j) * g[(*it).second + (*pt).second],
                s[j].insert({(*pt).first, (*pt).second + (*it).second}),
                s[j].erase(it), s[j].erase(pt);
          }
        }
      } else if (pval & (1LL << j) and !(val & (1LL << j))) {
        auto it = s[j].lower_bound({idx, -1});
        if (it != s[j].end() and (*it).first == idx) {
          if ((*it).second == 1)
            ans -= (1LL << j), s[j].erase({idx, 1});
          else
            ans -= (1LL << j) * ((*it).second),
                s[j].insert({idx + 1, (*it).second - 1}), s[j].erase(it);
        } else {
          it = prev(it);
          if ((*it).first + (*it).second - 1 == idx)
            ans -= (1LL << j) * ((*it).second),
                s[j].insert({(*it).first, (*it).second - 1}), s[j].erase(it);
          else {
            ans -= (1LL << j) * g[(*it).second],
                ans += (1LL << j) * g[idx - 1 - (*it).first + 1],
                ans +=
                (1LL << j) * g[(*it).first + (*it).second - 1 - idx - 1 + 1];
            s[j].insert({(*it).first, idx - 1 - (*it).first + 1}),
                s[j].insert(
                    {idx + 1, (*it).first + (*it).second - 1 - idx - 1 + 1}),
                s[j].erase(it);
          }
        }
      }
    }
    a[idx] = val;
    cout << ans << "\n";
  }
}