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 = 1e5 + 5;
int N, M, ql, qr, x, v, a[maxn], w, px, pv;
long long ans;
struct SEGMAX {
  int maxv[maxn << 2];
  inline void pushup(int o, int L, int R) {
    maxv[o] = max(maxv[o << 1], maxv[o << 1 | 1]);
  }
  void build(int o, int L, int R) {
    if (L == R) {
      maxv[o] = a[L] & (1 << w) ? 0 : L;
      return;
    }
    int M = (R + L) >> 1;
    build(o << 1, L, M);
    build(o << 1 | 1, M + 1, R);
    pushup(o, L, R);
  }
  void modify(int o, int L, int R) {
    if (L == R) {
      maxv[o] = v;
      return;
    }
    int M = (R + L) >> 1;
    if (x <= M) {
      modify(o << 1, L, M);
    } else {
      modify(o << 1 | 1, M + 1, R);
    }
    pushup(o, L, R);
  }
  int query(int o, int L, int R) {
    if (ql <= L && R <= qr) {
      return maxv[o];
    }
    int M = (R + L) >> 1, ret = 0;
    if (ql <= M) {
      ret = max(ret, query(o << 1, L, M));
    }
    if (M < qr) {
      ret = max(ret, query(o << 1 | 1, M + 1, R));
    }
    return ret;
  }
} segmax[17];
struct SEGMIN {
  int minv[maxn << 2];
  inline void pushup(int o, int L, int R) {
    minv[o] = min(minv[o << 1], minv[o << 1 | 1]);
  }
  void build(int o, int L, int R) {
    if (L == R) {
      minv[o] = a[L] & (1 << w) ? N + 1 : L;
      return;
    }
    int M = (R + L) >> 1;
    build(o << 1, L, M);
    build(o << 1 | 1, M + 1, R);
    pushup(o, L, R);
  }
  void modify(int o, int L, int R) {
    if (L == R) {
      minv[o] = v;
      return;
    }
    int M = (R + L) >> 1;
    if (x <= M) {
      modify(o << 1, L, M);
    } else {
      modify(o << 1 | 1, M + 1, R);
    }
    pushup(o, L, R);
  }
  int query(int o, int L, int R) {
    if (ql <= L && R <= qr) {
      return minv[o];
    }
    int M = (R + L) >> 1, ret = N + 1;
    if (ql <= M) {
      ret = min(ret, query(o << 1, L, M));
    }
    if (M < qr) {
      ret = min(ret, query(o << 1 | 1, M + 1, R));
    }
    return ret;
  }
} segmin[17];
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= N; ++i) {
    scanf("%d", &a[i]);
  }
  ++N;
  for (w = 0; w < 17; ++w) {
    segmax[w].build(1, 1, N);
    segmin[w].build(1, 1, N);
    for (int i = 1; i <= N; ++i) {
      if (a[i] & (1 << w)) {
        int L = i;
        while (i < N && a[i + 1] & (1 << w)) ++i;
        ans += (long long)(i - L + 1) * (i - L + 2) / 2 * (1 << w);
      }
    }
  }
  while (M--) {
    scanf("%d%d", &px, &pv);
    for (w = 0; w < 17; ++w) {
      if ((a[px] & (1 << w)) != (pv & (1 << w))) {
        if (a[px] & (1 << w)) {
          ql = 1, qr = px;
          int L = segmax[w].query(1, 1, N);
          ql = px, qr = N;
          int R = segmin[w].query(1, 1, N);
          if (R != L) {
            ans -= (long long)(R - L - 1) * (R - L) / 2 * (1 << w);
            ans += (long long)(px - L - 1) * (px - L) / 2 * (1 << w);
            ans += (long long)(R - px - 1) * (R - px) / 2 * (1 << w);
          }
          x = px, v = px;
          segmax[w].modify(1, 1, N);
          x = px, v = px;
          segmin[w].modify(1, 1, N);
        } else {
          int L = 0;
          if (px - 1 != 0) {
            ql = 1, qr = px - 1;
            L = segmax[w].query(1, 1, N);
          }
          ql = px + 1, qr = N;
          int R = segmin[w].query(1, 1, N);
          if (L != px - 1) {
            ans -= (long long)(px - L - 1) * (px - L) / 2 * (1 << w);
          }
          if (R != px + 1) {
            ans -= (long long)(R - px - 1) * (R - px) / 2 * (1 << w);
          }
          ans += (long long)(R - L - 1) * (R - L) / 2 * (1 << w);
          x = px, v = 0;
          segmax[w].modify(1, 1, N);
          x = px, v = N + 1;
          segmin[w].modify(1, 1, N);
        }
      }
    }
    a[px] = pv;
    printf("%I64d\n", ans);
  }
  return 0;
}