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;
int N, M, a[100100];
long long ans;
struct range {
  int s, e;
  bool operator<(const range &o) const { return s < o.s; }
};
set<range> c[17];
inline long long calc(int s, int e, int b) {
  long long x = e - s + 1;
  return (x * (x + 1) / 2) * (1LL << b);
}
set<range>::iterator lo, hi, h;
void add(int b, int i) {
  if (c[b].empty()) {
    ans += calc(i, i, b);
    c[b].insert({i, i});
    return;
  }
  int hs = 2e9, he = 2e9, ls = 2e9, le = 2e9;
  hi = c[b].end(), lo = c[b].end();
  hi = c[b].upper_bound({i, i});
  if (hi != c[b].begin()) lo = prev(hi);
  if (hi != c[b].end()) hs = hi->s, he = hi->e;
  if (lo != c[b].end()) ls = lo->s, le = lo->e;
  if (hs == i + 1 && le == i - 1) {
    ans -= calc(hs, he, b) + calc(ls, le, b);
    ans += calc(ls, he, b);
    c[b].erase(lo), c[b].erase(hi), c[b].insert({ls, he});
  } else if (hs == i + 1) {
    ans -= calc(hs, he, b);
    ans += calc(i, he, b);
    c[b].erase(hi), c[b].insert({i, he});
  } else if (le == i - 1) {
    ans -= calc(ls, le, b);
    ans += calc(ls, i, b);
    c[b].erase(lo), c[b].insert({ls, i});
  } else {
    ans += calc(i, i, b);
    c[b].insert({i, i});
  }
}
void remove(int b, int i) {
  h = --c[b].upper_bound({i, i});
  int s = h->s, e = h->e;
  ans -= calc(s, e, b);
  c[b].erase(h);
  if (i - 1 >= s) {
    ans += calc(s, i - 1, b);
    c[b].insert({s, i - 1});
  }
  if (i + 1 <= e) {
    ans += calc(i + 1, e, b);
    c[b].insert({i + 1, e});
  }
}
int main() {
  scanf("%d %d", &N, &M);
  for (int i = 0; i < (N); i++) {
    scanf("%d", &a[i]);
    for (int j = 0; j < (17); j++)
      if ((1 << j) & a[i]) {
        add(j, i);
      }
  }
  for (int i = 0; i < (M); i++) {
    int p, v;
    scanf("%d %d", &p, &v), p--;
    for (int j = 0; j < (17); j++)
      if ((1 << j) & a[p]) {
        remove(j, p);
      }
    a[p] = v;
    for (int j = 0; j < (17); j++)
      if ((1 << j) & a[p]) {
        add(j, p);
      }
    printf("%lld\n", ans);
  }
  return 0;
}