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:
//Author: net12k44
import java.io.*;
import java.util.*;
//public
class Main{//}

class data implements Comparable<data>{
	int le , ri;
	data() {}
	data(int left , int right) {le = left; ri = right;}
	public int size() {return ri - le + 1;}	
	public int compareTo(data X) { 
		return le - X.le;		
	}
	public boolean equals(data X) {return le == X.le;}

}

static final int maxBit = 17;
ArrayList< TreeSet<data> > s;
int a[];
long sum[];

int onBit( int num , int bit ){
	return num & (1 << bit);
}

long get(int n){
	return (long)n * (n+1) / 2;
}

private void add(int i , int value){
	for(int k = 0; k < maxBit; ++k)
	 if ( onBit(a[i] , k) != onBit(value , k) ){
		data now = new data(i , i);
		if (onBit(a[i] , k) == 0){			
			data le = s.get(k).lower( now );
			data ri = s.get(k).higher( now );
			
			int Left = i , Right = i;
			if (le != null && le.ri == i-1) {Left = le.le; sum[k] -= get( le.size() ); s.get(k).remove(le);}
			if (ri != null && ri.le == i+1) {Right= ri.ri; sum[k] -= get( ri.size() ); s.get(k).remove(ri);}
			now = new data(Left , Right);			
			sum[k] += get( now.size() ); s.get(k).add(now);			
		} else {			
			now = s.get(k).floor(now); 			
			int Left = now.le , Right = now.ri;
			sum[k] -= get( now.size() ); s.get(k).remove(now);
			if (Left <= i-1) {now = new data(Left , i-1); sum[k] += get( now.size() ); s.get(k).add(now);}
			if (Right>= i+1) {now = new data(i+1 ,Right); sum[k] += get( now.size() ); s.get(k).add(now);}
		}	
	}
	a[i] = value;	

}

private void solve() {
	
	s = new ArrayList< TreeSet<data> >();
	for(int i = 0; i < maxBit; ++i) s.add( new TreeSet<data>() ); 
	sum = new long[maxBit];
	
	int n = in.nextInt() , m = in.nextInt();
	a = new int[n];
	for(int i = 0; i < n; ++i)		
		add(i , in.nextInt() );		
		
	while (m-- > 0){
		add( in.nextInt()-1 , in.nextInt() );
		long kq = 0;
		for(int i = 0; i < maxBit; ++i) kq += sum[i] * (1 << i);		
		out.println(kq);
	}

}
	
public static void main (String[] args) throws java.lang.Exception {		
	long startTime = System.currentTimeMillis();

	out = new PrintWriter(System.out);
	new Main().solve();	
	//out.println((String.format("%.2f",(double)(System.currentTimeMillis()-startTime)/1000)));
	out.close();
}
static PrintWriter out;
static class in {
	static BufferedReader reader = new BufferedReader( new InputStreamReader(System.in) ) ;
	static StringTokenizer tokenizer = new StringTokenizer("");				
	static String next() {		
		while ( !tokenizer.hasMoreTokens() )
			try { tokenizer = new StringTokenizer( reader.readLine() ); }
			catch (IOException e){
				throw new RuntimeException(e);			
			}		
		return tokenizer.nextToken();
	}
	static int nextInt() { return Integer.parseInt( next() ); }		
	static double nextDouble(){ return Double.parseDouble( next() ); }
}
//////////////////////////////////////////////////
}//