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 MAXN = 1 << 17;
const int MAXLG = 20;
int n, m, a[MAXN];
bool b[MAXLG][MAXN];
struct data {
  long long sum, lt, num;
  data() {}
  data(long long _sum, long long _lt, long long _num)
      : sum(_sum), lt(_lt), num(_num) {}
} tree[MAXLG][2 * MAXN];
data prop(data d1, data d2, int lt, int mid, int rt) {
  return data(d1.sum + d2.sum + d1.num * (d2.lt - mid),
              d1.lt == mid ? d2.lt : d1.lt,
              d2.lt == rt ? d1.num + d2.num : d2.num);
}
void init(int c, int cur, int lt, int rt) {
  if (lt + 1 == rt)
    tree[c][cur] = data(b[c][lt], lt + b[c][lt], b[c][lt]);
  else {
    int mid = (lt + rt) / 2;
    init(c, 2 * cur, lt, mid);
    init(c, 2 * cur + 1, mid, rt);
    tree[c][cur] = prop(tree[c][2 * cur], tree[c][2 * cur + 1], lt, mid, rt);
  }
}
void update(int c, int cur, int lt, int rt, int p, int v) {
  if (lt + 1 == rt)
    tree[c][cur] = data(v, lt + v, v);
  else {
    int mid = (lt + rt) / 2;
    if (p < mid)
      update(c, 2 * cur, lt, mid, p, v);
    else
      update(c, 2 * cur + 1, mid, rt, p, v);
    tree[c][cur] = prop(tree[c][2 * cur], tree[c][2 * cur + 1], lt, mid, rt);
  }
}
int main() {
  ios ::sync_with_stdio(0);
  if (fopen("input.txt", "r")) freopen("input.txt", "r", stdin);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    for (int j = 0; j < MAXLG; j++) b[j][i] = a[i] & 1 << j;
  }
  for (int i = 0; i < MAXLG; i++) init(i, 1, 0, n);
  for (int i = 0; i < m; i++) {
    int p, v;
    cin >> p >> v;
    p--;
    long long ans = 0;
    for (int j = 0; j < MAXLG; j++) {
      update(j, 1, 0, n, p, bool(v & 1 << j));
      ans += tree[j][1].sum * (1 << j);
    }
    cout << ans << '\n';
  }
  return 0;
}