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 N = 100005;
const int LN = 17;
int arr[N];
int n, m;
set<pair<int, int> > s[LN];
long long ans = 0;
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &arr[i]);
  }
  for (int i = 0; i < LN; ++i) {
    int j = 1;
    while (j <= n && !((arr[j] >> i) & 1)) {
      ++j;
    }
    int start = j;
    int finish = j;
    for (; j <= n; ++j) {
      if (!((arr[j] >> i) & 1)) {
        finish = j - 1;
        if (finish >= start) {
          s[i].insert(make_pair(finish, start));
          ans += (1LL << i) *
                 ((1LL * (finish - start + 1) * (finish - start + 2)) >> 1);
        }
        start = j + 1;
      }
    }
    if ((arr[n] >> i) & 1) {
      finish = n;
      s[i].insert(make_pair(finish, start));
      ans += (1LL << i) *
             ((1LL * (finish - start + 1) * (finish - start + 2)) >> 1);
    }
  }
  while (m--) {
    int pos, val;
    scanf("%d %d", &pos, &val);
    for (int i = 0; i < LN; ++i) {
      if (((arr[pos] >> i) & 1) == ((val >> i) & 1)) {
        continue;
      } else {
        if ((arr[pos] >> i) & 1) {
          pair<int, int> temp = *s[i].lower_bound(make_pair(pos, -1));
          s[i].erase(s[i].find(temp));
          int start = temp.second;
          int finish = temp.first;
          ans -= (1LL << i) *
                 ((1LL * (finish - start + 1) * (finish - start + 2)) >> 1);
          finish = pos - 1;
          if (finish >= start) s[i].insert(make_pair(finish, start));
          ans += (1LL << i) *
                 ((1LL * (finish - start + 1) * (finish - start + 2)) >> 1);
          finish = temp.first;
          start = pos + 1;
          if (finish >= start) s[i].insert(make_pair(finish, start));
          ans += (1LL << i) *
                 ((1LL * (finish - start + 1) * (finish - start + 2)) >> 1);
        } else {
          if (pos == 1) {
            if ((arr[2] >> i) & 1) {
              pair<int, int> temp = *s[i].lower_bound(make_pair(pos, -1));
              s[i].erase(s[i].find(temp));
              int start = temp.second;
              int finish = temp.first;
              ans -= (1LL << i) *
                     ((1LL * (finish - start + 1) * (finish - start + 2)) >> 1);
              start = 1;
              ans += (1LL << i) *
                     ((1LL * (finish - start + 1) * (finish - start + 2)) >> 1);
              s[i].insert(make_pair(finish, start));
            } else {
              ans += 1 << i;
              s[i].insert(make_pair(1, 1));
            }
          } else if (pos == n && n > 1) {
            if ((arr[n - 1] >> i) & 1) {
              pair<int, int> temp = *s[i].lower_bound(make_pair(n - 1, -1));
              s[i].erase(s[i].find(temp));
              int start = temp.second;
              int finish = temp.first;
              ans -= (1LL << i) *
                     ((1LL * (finish - start + 1) * (finish - start + 2)) >> 1);
              finish = n;
              ans += (1LL << i) *
                     ((1LL * (finish - start + 1) * (finish - start + 2)) >> 1);
              s[i].insert(make_pair(finish, start));
            } else {
              ans += 1 << i;
              s[i].insert(make_pair(n, n));
            }
          } else if (n > 1) {
            if ((arr[pos - 1] >> i) & 1) {
              if ((arr[pos + 1] >> i) & 1) {
                pair<int, int> temp = *s[i].lower_bound(make_pair(pos - 1, -1));
                pair<int, int> temp2 =
                    *s[i].lower_bound(make_pair(pos + 1, -1));
                s[i].erase(s[i].find(temp));
                s[i].erase(s[i].find(temp2));
                int start = temp.second;
                int finish = temp.first;
                ans -=
                    (1LL << i) *
                    ((1LL * (finish - start + 1) * (finish - start + 2)) >> 1);
                start = temp2.second;
                finish = temp2.first;
                ans -=
                    (1LL << i) *
                    ((1LL * (finish - start + 1) * (finish - start + 2)) >> 1);
                start = temp.second;
                finish = temp2.first;
                s[i].insert(make_pair(finish, start));
                ans +=
                    (1LL << i) *
                    ((1LL * (finish - start + 1) * (finish - start + 2)) >> 1);
              } else {
                pair<int, int> temp = *s[i].lower_bound(make_pair(pos - 1, -1));
                s[i].erase(s[i].find(temp));
                int start = temp.second;
                int finish = temp.first;
                ans -=
                    (1LL << i) *
                    ((1LL * (finish - start + 1) * (finish - start + 2)) >> 1);
                finish = pos;
                s[i].insert(make_pair(finish, start));
                ans +=
                    (1LL << i) *
                    ((1LL * (finish - start + 1) * (finish - start + 2)) >> 1);
              }
            } else {
              if ((arr[pos + 1] >> i) & 1) {
                pair<int, int> temp = *s[i].lower_bound(make_pair(pos + 1, -1));
                s[i].erase(s[i].find(temp));
                int start = temp.second;
                int finish = temp.first;
                ans -=
                    (1LL << i) *
                    ((1LL * (finish - start + 1) * (finish - start + 2)) >> 1);
                start = pos;
                s[i].insert(make_pair(finish, start));
                ans +=
                    (1LL << i) *
                    ((1LL * (finish - start + 1) * (finish - start + 2)) >> 1);
              } else {
                ans += 1 << i;
                s[i].insert(make_pair(pos, pos));
              }
            }
          }
        }
      }
    }
    arr[pos] = val;
    printf("%lld\n", ans);
  }
}