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 JAVA):

Solution:
// practice with rainboy
import java.io.*;
import java.util.*;

public class CF400E extends PrintWriter {
	CF400E() { super(System.out); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF400E o = new CF400E(); o.main(); o.flush();
	}

	static final int K = 17;
	long[][] tr; int[][] pp, qq; int[] ss; int n_;
	void put(int i, int k) {
		tr[k][i] ^= 1; pp[k][i] ^= 1; qq[k][i] ^= 1;
	}
	void pul(int i, int k) {
		int l = i << 1, r = l | 1;
		tr[k][i] = tr[k][l] + tr[k][r] + (long) qq[k][l] * pp[k][r];
		pp[k][i] = pp[k][l] == ss[l] ? ss[l] + pp[k][r] : pp[k][l];
		qq[k][i] = qq[k][r] == ss[r] ? ss[r] + qq[k][l] : qq[k][r];
	}
	void init(int n) {
		n_ = 1;
		while (n_ < n)
			n_ <<= 1;
		tr = new long[K][n_ * 2];
		pp = new int[K][n_ * 2]; qq = new int[K][n_ * 2];
		ss = new int[n_ * 2];
		for (int i = 0; i < n_; i++)
			ss[n_ + i] = 1;
		for (int i = n_ - 1; i > 0; i--)
			ss[i] = ss[i << 1] + ss[i << 1 | 1];
	}
	void build(int[] aa, int n, int k) {
		for (int i = 0; i < n; i++)
			if ((aa[i] & 1 << k) != 0)
				put(n_ + i, k);
		for (int i = n_ - 1; i > 0; i--)
			pul(i, k);
	}
	void update(int i, int k) {
		put(i += n_, k);
		while (i > 1)
			pul(i >>= 1, k);
	}
	void main() {
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] aa = new int[n];
		for (int i = 0; i < n; i++)
			aa[i] = sc.nextInt();
		init(n);
		for (int k = 0; k < K; k++)
			build(aa, n, k);
		while (m-- > 0) {
			int i = sc.nextInt() - 1;
			int a = sc.nextInt() ^ aa[i];
			long ans = 0;
			for (int k = 0; k < K; k++) {
				if ((a & 1 << k) != 0)
					update(i, k);
				ans += tr[k][1] << k;
			}
			aa[i] ^= a;
			println(ans);
		}
	}
}