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:
import static java.lang.Math.*; 

import java.io.*; 
import java.util.*; 

public class Template {
	BufferedReader in; 
	PrintWriter out;
	StringTokenizer st; 

	String next() {
		while (st==null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(in.readLine());
			} catch (Exception e) {}
		}
		return st.nextToken(); 
	}

	int nextInt() {
		return Integer.parseInt(next()); 
	}

	long nextLong() {
		return Long.parseLong(next());
	}

	double nextDouble() {
		return Double.parseDouble(next());
	}

	int[] a; 
	int n,m; 
	Tree[] t; 
	class Tree {
		int[] le, ri; 
		long[] s; 
		boolean[] all; 

		public Tree(int n) {
	//		a = new int[4 * n]; 
			le = new int[4 * n]; 
			ri = new int[4 * n]; 
			s = new long[4 * n]; 
			all = new boolean[4 * n]; 
		}

		public void update(int p, int v) {
			update(1, 1, n, p, v);
		}

		public void update(int v, int l, int r, int p, int val) {
			if (l > p || r < p) return;
			if (l == r) {
				//a[v] = val; 
				if (val == 1) le[v] = 1; else le[v] = 0; 
				if (val == 1) ri[v] = 1; else ri[v] = 0; 
				if (val == 1) s[v] = 1; else s[v] = 0; 
				if (val == 1) all[v] = true; else all[v] = false; 
				return;
			}
			int m = (l+r) / 2; 
			update(v*2, l, m, p, val);
			update(v*2+1, m+1, r, p, val);
			long sl = s[v*2] - ri[v*2]*(ri[v*2] + 1L)/2; 
			long sr = s[v*2+1] - le[v*2+1]*(le[v*2+1] + 1L)/2; 
			long mid = ri[v*2] + le[v*2+1]; 
			mid = mid * (mid + 1L) / 2; 
			s[v] = sl + sr + mid; 
			all[v] = all[v*2] & all[v*2+1];
			ri[v] = ri[v*2+1] + (all[v*2+1] ? ri[v*2] : 0); 
			le[v] = le[v*2] + (all[v*2] ? le[v*2+1] : 0); 
		}
	}

	int bit(int x, int p) {
		if ((x & (1 << p)) > 0) return 1; else return 0;
	}

	public void run() throws Exception {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		Long start = System.currentTimeMillis();
			n = nextInt(); 
			m = nextInt(); 
			a = new int[n+1]; 
			t = new Tree[17]; 
			for (int i=0; i<17; i++) t[i] = new Tree(n);

			for (int i=1; i<=n; i++) {
				a[i] = nextInt();
				for (int j=0; j<17; j++) if (bit(a[i], j) > 0) t[j].update(i, 1);
			}

			for (int i=0; i<m; i++) {
				int p = nextInt(); 
				int v = nextInt(); 
				long ans=0; 
				for (int j=0; j<17; j++) {
					if (bit(a[p], j) != bit(v, j)) t[j].update(p, bit(v, j));
					ans += (1L << j) * t[j].s[1]; 
				}
				a[p] = v;
				out.println(ans);
			}



		Long end = System.currentTimeMillis();

		//System.out.println((end - start) / 1000.0);
		out.close(); 
	}

	public static void main(String[] args) throws Exception {
		new Template().run(); 
	}
}