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 MAXN = 1e5 + 5;
const long long MAXBIT = 17;
const long long INF = 1e9;
long long N, M;
long long A[MAXN];
set<pair<long long, long long>> intervals[MAXBIT];
long long totCnt[MAXN];
void replace(pair<long long, long long> a, pair<long long, long long> b,
             long long bit) {
  long long dista = a.second - a.first;
  long long distb = b.second - b.first;
  intervals[bit].insert(b);
  intervals[bit].erase(a);
  totCnt[bit] -= dista * (dista + 1) / 2;
  totCnt[bit] += distb * (distb + 1) / 2;
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> N >> M;
  for (long long i = 0; i < N; i++) {
    cin >> A[i];
  }
  for (long long b = 0; b < MAXBIT; b++) {
    long long cnt = 0;
    long long curCnt = 0;
    bool inOne = false;
    for (long long i = 0; i < N; i++) {
      if ((A[i] & (1 << b)) != 0) {
        if (!inOne) {
          inOne = true;
        }
        curCnt++;
      } else {
        if (inOne) {
          intervals[b].insert({i - curCnt, i});
          cnt += curCnt * (curCnt + 1) / 2;
          curCnt = 0;
          inOne = false;
        }
      }
    }
    if (inOne) {
      intervals[b].insert({N - curCnt, N});
      cnt += curCnt * (curCnt + 1) / 2;
    }
    totCnt[b] = cnt;
  }
  for (long long t = 0; t < M; t++) {
    long long p, v;
    cin >> p >> v;
    p--;
    A[p] = v;
    for (long long b = 0; b < MAXBIT; b++) {
      if ((A[p] & (1 << b)) != 0) {
        if (intervals[b].size() == 0) {
          intervals[b].insert({p, p + 1});
          totCnt[b] += 1;
          continue;
        }
        auto cur = intervals[b].lower_bound({p, INF});
        if (cur != intervals[b].begin()) cur--;
        auto nxt = next(cur);
        if ((nxt == intervals[b].end() || nxt->first > p + 1) &&
            cur->second < p) {
          intervals[b].insert({p, p + 1});
          totCnt[b] += 1;
        } else if (cur->first <= p && cur->second > p) {
          continue;
        } else {
          if (cur->second == p &&
              (nxt != intervals[b].end() && nxt->first == p + 1)) {
            totCnt[b] -=
                (cur->second - cur->first) * (cur->second - cur->first + 1) / 2;
            totCnt[b] -=
                (nxt->second - nxt->first) * (nxt->second - nxt->first + 1) / 2;
            totCnt[b] +=
                (nxt->second - cur->first) * (nxt->second - cur->first + 1) / 2;
            intervals[b].insert({cur->first, nxt->second});
            intervals[b].erase(cur);
            intervals[b].erase(nxt);
          } else if (cur->second == p) {
            replace(*cur, {cur->first, p + 1}, b);
          } else if (nxt != intervals[b].end() && nxt->first == p + 1) {
            replace(*nxt, {p, nxt->second}, b);
          } else if (cur == intervals[b].begin() && cur->first == p + 1) {
            replace(*cur, {p, cur->second}, b);
          } else if (cur == intervals[b].begin() && cur->first > p + 1) {
            intervals[b].insert({p, p + 1});
            totCnt[b] += 1;
          }
        }
      } else {
        if (intervals[b].size() == 0) continue;
        auto cur = intervals[b].lower_bound({p, INF});
        if (cur != intervals[b].begin()) cur--;
        if (cur->first <= p && cur->second > p) {
          totCnt[b] -=
              (cur->second - cur->first) * (cur->second - cur->first + 1) / 2;
          totCnt[b] += (p - cur->first) * (p - cur->first + 1) / 2;
          totCnt[b] +=
              (cur->second - (p + 1)) * (cur->second - (p + 1) + 1) / 2;
          if (p != cur->first) intervals[b].insert({cur->first, p});
          if (p + 1 != cur->second) intervals[b].insert({p + 1, cur->second});
          intervals[b].erase(cur);
        }
      }
    }
    long long ans = 0;
    for (long long b = 0; b < MAXBIT; b++) {
      ans += (totCnt[b] * (1 << b));
    }
    cout << ans << endl;
  }
}