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>
struct sNode {
  int l, r;
  sNode* pl;
  sNode* pr;
  int val;
};
void buildTree(sNode* root) {
  root->pl = (sNode*)malloc(sizeof(sNode));
  root->pl->l = root->l;
  root->pl->r = (root->l + root->r) / 2;
  root->pl->pl = root->pl->pr = NULL;
  root->pl->val = 0;
  if (root->pl->l < root->pl->r) buildTree(root->pl);
  root->pr = (sNode*)malloc(sizeof(sNode));
  root->pr->l = root->pl->r + 1;
  root->pr->r = root->r;
  root->pr->pl = root->pr->pl = NULL;
  root->pr->val = 0;
  if (root->pr->l < root->pr->r) buildTree(root->pr);
}
void resetTree(sNode* root) {
  root->val = 0;
  if (root->l < root->r) {
    resetTree(root->pl);
    resetTree(root->pr);
  }
}
void updateTree(int l, int r, int val, sNode* root) {
  if (l <= root->l && r >= root->r) {
    root->val += val;
    return;
  }
  if (l <= root->pl->r && root->pl->l <= r) updateTree(l, r, val, root->pl);
  if (l <= root->pr->r && root->pr->l <= r) updateTree(l, r, val, root->pr);
}
int getVal(int i, sNode* root) {
  int ans = root->val;
  while (root->l < root->r) {
    if (root->pl->l <= i && i <= root->pl->r)
      root = root->pl;
    else
      root = root->pr;
    ans += root->val;
  }
  return ans;
}
bool marked[100000];
struct sQuery {
  int p, v;
};
int input[100000];
sQuery queries[100000];
long long ans[100000];
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d", &input[i]);
  }
  for (int j = 0; j < m; j++) {
    scanf("%d %d", &queries[j].p, &queries[j].v);
    queries[j].p--;
  }
  sNode* cntLeft = (sNode*)malloc(sizeof(sNode));
  cntLeft->l = 0;
  cntLeft->r = n - 1;
  cntLeft->val = 0;
  buildTree(cntLeft);
  sNode* cntRight = (sNode*)malloc(sizeof(sNode));
  cntRight->l = 0;
  cntRight->r = n - 1;
  cntRight->val = 0;
  buildTree(cntRight);
  for (int t = 0; t < 18; t++) {
    resetTree(cntLeft);
    resetTree(cntRight);
    for (int i = 0; i < n; i++) {
      marked[i] = (input[i] & (1 << t));
    }
    int l = 0;
    for (int i = 0; i < n; i++) {
      if (!marked[i]) {
        l = i + 1;
      } else {
        updateTree(l, i, 1, cntRight);
      }
    }
    int r = n - 1;
    for (int i = n - 1; i >= 0; i--) {
      if (!marked[i]) {
        r = i - 1;
      } else {
        updateTree(i, r, 1, cntLeft);
      }
    }
    long long tmpAns = 0;
    for (int i = 0; i < n; i++) {
      tmpAns += (long long)getVal(i, cntRight);
    }
    for (int i = 0; i < m; i++) {
      if (marked[queries[i].p] && !(queries[i].v & (1 << t))) {
        marked[queries[i].p] = false;
        int a = (queries[i].p > 0 ? getVal(queries[i].p - 1, cntLeft) : 0);
        int b = (queries[i].p < n - 1 ? getVal(queries[i].p + 1, cntRight) : 0);
        tmpAns -= (long long)(a + 1) * (long long)(b + 1);
        updateTree(queries[i].p - a, queries[i].p, -b - 1, cntRight);
        updateTree(queries[i].p, queries[i].p + b, -a - 1, cntLeft);
      } else if (!marked[queries[i].p] && (queries[i].v & (1 << t))) {
        marked[queries[i].p] = true;
        int a = (queries[i].p > 0 ? getVal(queries[i].p - 1, cntLeft) : 0);
        int b = (queries[i].p < n - 1 ? getVal(queries[i].p + 1, cntRight) : 0);
        tmpAns += (long long)(a + 1) * (long long)(b + 1);
        updateTree(queries[i].p - a, queries[i].p, b + 1, cntRight);
        updateTree(queries[i].p, queries[i].p + b, a + 1, cntLeft);
      }
      ans[i] += tmpAns * (1LL << t);
    }
  }
  for (int i = 0; i < m; i++) {
    printf("%I64d\n", ans[i]);
  }
}