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;
struct {
  int from, to;
  pair<int, int> arr[21];
} tree[1001000];
int n, m, a[1001000];
void make_a_tree(int left, int right, int node) {
  tree[node].from = left;
  tree[node].to = right;
  int i, div;
  if (left == right) {
    for (i = 0; i < 20; i++) {
      if ((a[left] >> i) & 1) {
        tree[node].arr[i] = make_pair(left, left);
      } else {
        tree[node].arr[i] = make_pair(left - 1, left + 1);
      }
    }
    return;
  }
  div = (left + right) / 2;
  make_a_tree(left, div, node + node);
  make_a_tree(div + 1, right, node + node + 1);
  for (i = 0; i < 20; i++) {
    if (tree[node + node].arr[i].first == div) {
      tree[node].arr[i].first = tree[node + node + 1].arr[i].first;
    } else {
      tree[node].arr[i].first = tree[node + node].arr[i].first;
    }
    if (tree[node + node + 1].arr[i].second == div + 1) {
      tree[node].arr[i].second = tree[node + node].arr[i].second;
    } else {
      tree[node].arr[i].second = tree[node + node + 1].arr[i].second;
    }
  }
  return;
}
pair<int, int> query(int left, int right, int node, int ind) {
  if (tree[node].from == left && tree[node].to == right) {
    return tree[node].arr[ind];
  }
  int div;
  div = (tree[node].from + tree[node].to) / 2;
  if (right <= div) {
    return query(left, right, node + node, ind);
  } else if (left > div) {
    return query(left, right, node + node + 1, ind);
  } else {
    pair<int, int> ele1, ele2, ans;
    ele1 = query(left, div, node + node, ind);
    ele2 = query(div + 1, right, node + node + 1, ind);
    if (ele1.first == div) {
      ans.first = ele2.first;
    } else {
      ans.first = ele1.first;
    }
    if (ele2.second == div + 1) {
      ans.second = ele1.second;
    } else {
      ans.second = ele2.second;
    }
    return ans;
  }
}
void update(int node, int dist, int ind) {
  if (tree[node].from == tree[node].to) {
    tree[node].arr[ind].first = dist + dist - tree[node].arr[ind].first - 1;
    tree[node].arr[ind].second = dist + dist - tree[node].arr[ind].second + 1;
    return;
  }
  int div;
  div = (tree[node].from + tree[node].to) / 2;
  if (dist <= div) {
    update(node + node, dist, ind);
  } else {
    update(node + node + 1, dist, ind);
  }
  if (tree[node + node].arr[ind].first == div) {
    tree[node].arr[ind].first = tree[node + node + 1].arr[ind].first;
  } else {
    tree[node].arr[ind].first = tree[node + node].arr[ind].first;
  }
  if (tree[node + node + 1].arr[ind].second == div + 1) {
    tree[node].arr[ind].second = tree[node + node].arr[ind].second;
  } else {
    tree[node].arr[ind].second = tree[node + node + 1].arr[ind].second;
  }
}
int main() {
  int i, j, k, x, val;
  scanf("%d %d", &n, &m);
  for (i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  long long sum, cnt, lc, power[22], early, now, l, r;
  pair<int, int> ele1, ele2;
  sum = 0;
  power[0] = 1;
  for (i = 1; i <= 20; i++) {
    power[i] = power[i - 1] + power[i - 1];
  }
  for (i = 0; i < 20; i++) {
    cnt = 0;
    lc = 0;
    for (j = 0; j < n; j++) {
      if ((a[j] >> i) & 1) {
        cnt++;
      } else {
        lc += (cnt * (cnt + 1)) / 2;
        cnt = 0;
      }
    }
    lc += (cnt * (cnt + 1)) / 2;
    sum += power[i] * lc;
  }
  make_a_tree(0, n - 1, 1);
  for (i = 0; i < m; i++) {
    scanf("%d %d", &x, &val);
    x--;
    for (j = 0; j < 20; j++) {
      if (((val >> j) & 1) && (!((a[x] >> j) & 1))) {
        if (x != 0)
          ele1 = query(0, x - 1, 1, j);
        else
          ele1 = make_pair(0, 0);
        if (x != n - 1)
          ele2 = query(x + 1, n - 1, 1, j);
        else
          ele2 = make_pair(n - 1, n - 1);
        l = x - ele1.second;
        r = ele2.first - x;
        early = (l * (l + 1)) / 2 + (r * (r + 1)) / 2;
        now = l + r + 1;
        now = (now * (now + 1)) / 2;
        sum += (now - early) * power[j];
        update(1, x, j);
      } else if ((!((val >> j) & 1)) && ((a[x] >> j) & 1)) {
        if (x != 0)
          ele1 = query(0, x - 1, 1, j);
        else
          ele1 = make_pair(0, 0);
        if (x != n - 1)
          ele2 = query(x + 1, n - 1, 1, j);
        else
          ele2 = make_pair(n - 1, n - 1);
        l = x - ele1.second;
        r = ele2.first - x;
        early = l + r + 1;
        now = (l * (l + 1)) / 2 + (r * (r + 1)) / 2;
        early = (early * (early + 1)) / 2;
        sum += (now - early) * power[j];
        update(1, x, j);
      }
    }
    a[x] = val;
    cout << sum << endl;
  }
}