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;
template <typename T, typename U>
void upmin(T& a, const U& b) {
  a = min<T>(a, b);
}
template <typename T, typename U>
void upmax(T& a, const U& b) {
  a = max<T>(a, b);
}
template <typename T>
void uniq(T& a) {
  sort(a.begin(), a.end());
  a.erase(unique(a.begin(), a.end()), a.end());
}
template <class T>
string to_s(const T& a) {
  ostringstream os;
  os << a;
  return os.str();
}
template <class T>
T to_T(const string& s) {
  istringstream is(s);
  T res;
  is >> res;
  return res;
}
void fast_io() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}
bool in_rect(int x, int y, int w, int h) {
  return 0 <= x && x < w && 0 <= y && y < h;
}
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
long long left(const set<int>& s, int k) {
  auto it = s.lower_bound(k);
  if (*it >= k) --it;
  return *it;
}
long long right(const set<int>& s, int k) {
  auto it = s.upper_bound(k);
  return *it;
}
const int B = 17;
long long diff_by_bit_query(set<int>& zero_pos, int p, int bit) {
  int current_bit = zero_pos.count(p) ? 0 : 1;
  if (current_bit == bit) return 0;
  long long l = p - left(zero_pos, p);
  long long r = right(zero_pos, p) - p;
  long long diff = l * r;
  if (bit == 0) {
    zero_pos.insert(p);
    return -diff;
  } else {
    zero_pos.erase(p);
    return diff;
  }
}
long long diff_by_query(vector<set<int>>& zero_poses, int p, int v) {
  long long sum_diff = 0;
  for (int i = 0; i < (int)(B); ++i)
    sum_diff += (1LL << i) * diff_by_bit_query(zero_poses[i], p, v >> i & 1);
  return sum_diff;
}
int main() {
  fast_io();
  int n, m;
  cin >> n >> m;
  vector<set<int>> zero_poses(B);
  for (int i = 0; i < (int)(B); ++i) {
    for (int p = -1; p <= n; ++p) zero_poses[i].insert(p);
  }
  long long sum = 0;
  for (int i = 0; i < (int)(n); ++i) {
    int a;
    cin >> a;
    sum += diff_by_query(zero_poses, i, a);
  }
  for (int qi = 0; qi < (int)(m); ++qi) {
    int p, v;
    cin >> p >> v;
    --p;
    sum += diff_by_query(zero_poses, p, v);
    cout << sum << endl;
  }
}