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 java.util.*;
import java.io.*;

public class Main {
	
    public static void main(String[] args) {
    	
    	PrintWriter pf = new PrintWriter(System.out);
        fastget sf = new fastget();
        segmenttree[] sgt = new segmenttree[17]; 
        int n = sf.nextInt(),m = sf.nextInt();
        int[] a = new int[n+5];
        for(int i=0;i<17;++i)
        	sgt[i] = new segmenttree(n*2+5);
        for(int i=1;i<=n;++i) {
        	a[i] = sf.nextInt();
        	int x = a[i];
        	for(int j=0;j<17;++j) {
        		if((x&1)==1) sgt[j].update(1,n,i,x&1);
        		x>>=1;
        	}
        }
        for(int i=1;i<=m;++i) {
        	int c = sf.nextInt();
        	int x = sf.nextInt();
        	int id = sgt[0].id(1,n);
        	long ans = 0;
        	for(int j=0;j<17;++j) {
        		if((a[c]&(1<<j))!=(x&(1<<j))) sgt[j].update(1,n,c,(x>>j)&1);
        		ans+=sgt[j].ss[id]*(1<<j);
        	}
        	a[c]=x;
        	pf.println(ans);
        }
        pf.close();
    }
}

class fastget {
	
	public BufferedReader in;
	public StringTokenizer st;
	
	public fastget() {
		in = new BufferedReader(new InputStreamReader(System.in));
	}
	
	private String next() {
		while (st==null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(in.readLine());
			} catch (Exception e) {}
		}
		return st.nextToken(); 
	}
	
	public int nextInt() {
		return Integer.parseInt(next());
	}
	
	public long nextLong() {
		return Long.parseLong(next());
	}
	
	public double nextDouble() {
		return Double.parseDouble(next());
	}
	
}

class segmenttree {
	
	public segmenttree(int n){
		ls = new int[n];
		rs = new int[n];
		ss = new long[n];
	}
	
	public int id(int l,int r) {
		return l+r | (l!=r?1:0);
	}
	
	public void update(int l,int r,int i,int x) {
		int rt = id(l,r);
		if(l==r) {
			if(x==1) ss[rt]=ls[rt]=rs[rt]=1;
			else ss[rt]=ls[rt]=rs[rt]=0;
			return;
		}
		int mid=l+r>>1;
		if(i<=mid) update(l,mid,i,x);
		else update(mid+1,r,i,x);
		int rtl = id(l,mid),rtr = id(mid+1,r);
		ss[rt] = ss[rtl]+ss[rtr]+(rs[rtl]+ls[rtr]+1L)*(rs[rtl]+ls[rtr])/2;
		ss[rt] -= (rs[rtl]+1L)*rs[rtl]/2;
		ss[rt] -= (ls[rtr]+1L)*ls[rtr]/2;
		if(ls[rtl]==mid-l+1) ls[rt] = ls[rtl]+ls[rtr];
		else ls[rt] = ls[rtl];
		if(rs[rtr]==r-mid) rs[rt] = rs[rtr]+rs[rtl];
		else rs[rt] = rs[rtr];
	}
	 
	public int[] ls;
	public int[] rs;
	public long[] ss;
}