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 E {
    static int[] in;
    static int[] exps = new int[17];
    static long totSum;
    static TreeMap<Integer, Integer>[] map;
    static int[] ms;

    public static void main(String[] args) {
	for(int i = 0; i < exps.length; i++) {
	    exps[i] = 1 << i;
	}
	
	IO io = new IO(System.in, System.out);    
	int n = io.nextInt();
	int m = io.nextInt();
	in = new int[n];
	ms = new int[m+m];
	map = (TreeMap<Integer, Integer>[]) new TreeMap[exps.length];

	for (int i = 0; i < in.length; i++)
	    in[i] = io.nextInt();
	for (int i = 0; i < ms.length; i++)
	    ms[i] = io.nextInt();
	initMap();

	for(int i = 0; i < ms.length;) {
	    int pi = ms[i++];
	    int vi = ms[i++];
	    in[pi-1] = vi;
	    update(pi-1);
	    io.println(totSum >> 1);
	}
	io.flush();
    }

    public static void rem(int i, int key) {
	long value = map[i].remove(key);
	totSum -= ((long) value*(value+1)) << (i);
    }
    
    public static void add(int i, int key,  int value) {
	map[i].put(key, value);
	totSum += ((long) value*(value+1)) << (i);
    }
    
    public static void update (int index) {
	for (int i = 0; i < exps.length; i++) {
	    Map.Entry<Integer, Integer> low = map[i].floorEntry(index);
	    Map.Entry<Integer, Integer> high = map[i].ceilingEntry(index);
	    if ((in[index] & exps[i]) > 0) { // a one maybe join something
		int start = index;
		int l = 1;

		if (low != null) {
		    int key = low.getKey();
		    int val = low.getValue();
		    if(key + val - 1 >= index) {
			continue; // previous value was 1
		    } else if(key + val - 1 == index - 1) {
			start = key;
			l += val;
			rem(i, key);
		    }
		}
		if (high != null) {
		    int key = high.getKey();
		    int val = high.getValue();
		    if (key == index + 1) { // should join for a larger sequence
			l += val;
			rem(i, key);
		    }
		}
		add(i, start, l);
	    } else { // a zero : maybe split something
		if (low != null) {
		    int key = low.getKey();
		    int val = low.getValue();
		    if(key + val - 1 < index) { // previous value was 0
			continue; 
		    } else {
			rem(i, key);
			int newLowValue = index - key;
			int newHighValue = val + key - index - 1;
			if (newLowValue > 0) {
			    add(i, key, newLowValue);
			} 
			if (newHighValue > 0) {
			    add(i,index+1, newHighValue);
			}
		    }
		}
	    }	 
	}
    } 
    
    
    public static void initMap () {		
	totSum = 0;
	for (int bit = 0; bit < exps.length; bit++) {
	    map[bit] = new TreeMap<Integer,Integer>();
	    int l = 0;
	    for (int i = 0; i <= in.length; i++) {
		if (i < in.length && ((exps[bit] & in[i]) > 0)) {
		    l++;
		} else if(l > 0) {
			add(bit, i-l, l);
			l = 0;
		}
	    }
	}
    }
}


class IO extends PrintWriter{
    BufferedReader reader;
    StringTokenizer tokenizer;
    private String newLine = System.getProperty("line.separator");

    IO (InputStream in, OutputStream out) {
	super(new BufferedWriter(new PrintWriter(out)));
	reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = new StringTokenizer("");
    }
    
    public void println(CharSequence seq) {
	print(seq);
	print(newLine);
    }
    
    String next() {
	try{
	    while (!tokenizer.hasMoreTokens())
		tokenizer = new StringTokenizer(reader.readLine());
	    return tokenizer.nextToken();
	} catch (IOException e) {throw new RuntimeException();}
    }
    
    int nextInt() {
        return Integer.parseInt(next());
    }
    
    double nextDouble(){
        return Double.parseDouble(next());
    }
}