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 treap {
  struct treapnode {
    int sz, pri, ch[2], l, r;
  } t[100010];
  int root, tot;
  long long ans;
  inline void upd(int x) {
    if (x) t[x].sz = t[t[x].ch[0]].sz + t[t[x].ch[1]].sz + 1;
  }
  void rot(int &x, int f) {
    int y = t[x].ch[!f];
    t[x].ch[!f] = t[y].ch[f];
    t[y].ch[f] = x;
    upd(x);
    upd(y);
    x = y;
  }
  void ins(int &x, int il, int ir) {
    if (!x)
      t[x = ++tot] = (treapnode){1, rand(), {0, 0}, il, ir};
    else {
      int f = (il < t[x].l);
      ins(t[x].ch[!f], il, ir);
      if (t[t[x].ch[!f]].pri > t[x].pri) rot(x, f);
    }
    upd(x);
  }
  void del(int &x, int il) {
    if (t[x].l == il) {
      if (!t[x].ch[0] || !t[x].ch[1])
        x = t[x].ch[0] + t[x].ch[1];
      else {
        int f = (t[t[x].ch[0]].pri > t[t[x].ch[1]].pri);
        rot(x, f);
        del(t[x].ch[f], il);
      }
    } else {
      int f = (t[x].l > il);
      del(t[x].ch[!f], il);
    }
    upd(x);
  }
  int findkth(int k) {
    int x = root;
    while (t[t[x].ch[0]].sz + 1 != k) {
      if (k < t[t[x].ch[0]].sz + 1)
        x = t[x].ch[0];
      else
        k -= (t[t[x].ch[0]].sz + 1), x = t[x].ch[1];
    }
    return x;
  }
  void travel(int x) {
    if (!x) return;
    cout << "(";
    cout << "(";
    travel(t[x].ch[0]);
    cout << ")";
    cout << t[x].l;
    cout << "(";
    travel(t[x].ch[1]);
    cout << ")";
    cout << ")";
  }
  int find(int il) {
    int x = root, sz = 0;
    while (x) {
      if (t[x].l <= il)
        sz += t[t[x].ch[0]].sz + 1, x = t[x].ch[1];
      else
        x = t[x].ch[0];
    }
    return sz;
  }
  inline void Ins(int il, int ir) {
    ins(root, il, ir);
    ans += 1ll * (ir - il + 2) * (ir - il + 1) / 2;
  }
  inline void Del(int il, int ir) {
    del(root, il);
    ans -= 1ll * (ir - il + 2) * (ir - il + 1) / 2;
  }
} T[17];
int n, a[17][100010], Q;
int main() {
  scanf("%d%d", &n, &Q);
  int x, y;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &x);
    int cnt = 0;
    for (; x; x >>= 1) a[cnt++][i] = x & 1;
  }
  for (int i = 0; i < 17; i++) {
    T[i].root = T[i].tot = 0;
    T[i].ans = 0;
    T[i].Ins(0, 0);
    T[i].Ins(n + 1, n + 1);
    int la = 0;
    for (int j = 1; j <= n; j++) {
      if (la && a[i][j] == 0)
        T[i].Ins(la, j - 1), la = 0;
      else if (!la && a[i][j] == 1)
        la = j;
    }
    if (a[i][n] == 1) T[i].Ins(la, n);
  }
  while (Q--) {
    scanf("%d%d", &x, &y);
    long long curans = 0;
    for (int i = 0; i < 17; i++) {
      int tmp = y & 1;
      y >>= 1;
      if (a[i][x] == tmp) {
        curans += 1ll * (1 << i) * (T[i].ans - 2);
        continue;
      }
      if (a[i][x] == 1) {
        int u = T[i].find(x);
        int k = T[i].findkth(u);
        int l1 = T[i].t[k].l, r2 = T[i].t[k].r;
        T[i].Del(l1, r2);
        int r1 = x - 1, l2 = x + 1;
        if (l1 <= r1) T[i].Ins(l1, r1);
        if (l2 <= r2) T[i].Ins(l2, r2);
      } else {
        int u = T[i].find(x);
        int k = T[i].findkth(u);
        int l1 = T[i].t[k].l, r1 = T[i].t[k].r;
        k = T[i].findkth(u + 1);
        int l2 = T[i].t[k].l, r2 = T[i].t[k].r;
        if (l1 == 0 && l2 == n + 1) {
          T[i].Ins(x, x);
        } else if (l1 == 0) {
          if (x + 1 == l2) {
            T[i].Del(l2, r2);
            T[i].Ins(x, r2);
          } else {
            T[i].Ins(x, x);
          }
        } else if (l2 == n + 1) {
          if (x - 1 == r1) {
            T[i].Del(l1, r1);
            T[i].Ins(l1, x);
          } else {
            T[i].Ins(x, x);
          }
        } else {
          if (x - 1 == r1 && x + 1 == l2) {
            T[i].Del(l1, r1);
            T[i].Del(l2, r2);
            T[i].Ins(l1, r2);
          } else if (x - 1 == r1) {
            T[i].Del(l1, r1);
            T[i].Ins(l1, x);
          } else if (x + 1 == l2) {
            T[i].Del(l2, r2);
            T[i].Ins(x, r2);
          } else
            T[i].Ins(x, x);
        }
      }
      curans += 1ll * (1 << i) * (T[i].ans - 2);
      a[i][x] = tmp;
    }
    printf("%I64d\n", curans);
  }
  return 0;
}