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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Collection;
import java.util.Locale;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	public static void main(String[] args) throws IOException {
		new Thread(null, new Runnable() {
			public void run() {
				try {
					long prevTime = System.currentTimeMillis();
					new Main().run();
					System.err.println("Total time: "
							+ (System.currentTimeMillis() - prevTime) + " ms");
					System.err.println("Memory status: " + memoryStatus());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}, "1", 1L << 24).start();
	}

	void run() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		Object o = solve();
		if (o != null)
			out.println(o);
		out.close();
		in.close();
	}

	private Object solve() throws IOException {
		int n = ni();
		int k = 20;
		int m = ni();

		boolean[][] bits = new boolean[k][n + 2];
		TreeSet<Integer>[] zeros = (TreeSet<Integer>[]) new TreeSet[k];
		for (int i = 0; i < k; i++) {
			zeros[i] = new TreeSet<Integer>();
			zeros[i].add(0);
			zeros[i].add(n + 1);

		}
		for (int i = 1; i <= n; i++) {
			int a = ni();
			for (int j = 0; j < k; j++)
				if (((1 << j) & a) == 0) {
					zeros[j].add(i);
				} else {
					bits[j][i] = true;
				}

		}
		long[] acum = new long[k];
		for (int exp = 0; exp < k; exp++) {
			int i = 1;
			while (i <= n) {

				while (i <= n && !bits[exp][i])
					i++;
				int j = i;
				while (j <= n + 1 && bits[exp][j])
					j++;
				if (i != n + 1)
					acum[exp] += f(j - i);
				i = j;
			}

		}

		for (int i = 0; i < m; i++) {
			int index = ni();
			int value = ni();
			for (int exp = 0; exp < k; exp++) {
				TreeSet<Integer> this_zeros = zeros[exp];
				boolean prev_set = bits[exp][index];
				boolean set = (value & (1 << exp)) != 0;
				if (prev_set == set)
					continue;
				if (prev_set) {
					int prev_zero = this_zeros.lower(index);
					int next_zero = this_zeros.higher(index);
					acum[exp] += f(index - prev_zero - 1)
							+ f(next_zero - index - 1)
							- f(next_zero - prev_zero - 1);
					this_zeros.add(index);
					bits[exp][index] = false;
				} else {
					this_zeros.remove(index);
					int prev_zero = this_zeros.lower(index);
					int next_zero = this_zeros.higher(index);
					acum[exp] += f(next_zero - prev_zero - 1)
							- f(index - prev_zero - 1)
							- f(next_zero - index - 1);
					bits[exp][index] = true;
				}

			}
			out.println(ans(acum));
		}

		return null;
	}

	private long ans(long[] acum) {
		long ret = 0;
		for (int exp = 0; exp < acum.length; exp++)
			ret += acum[exp] << exp;
		return ret;
	}

	private long f(long n) {
		return ((n + 1L) * n) / 2L;
	}

	BufferedReader in;
	PrintWriter out;
	StringTokenizer strTok = new StringTokenizer("");

	String nextToken() throws IOException {
		while (!strTok.hasMoreTokens())
			strTok = new StringTokenizer(in.readLine());
		return strTok.nextToken();
	}

	int ni() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nl() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nd() throws IOException {
		return Double.parseDouble(nextToken());
	}

	int[] nia(int size) throws IOException {
		int[] ret = new int[size];
		for (int i = 0; i < size; i++)
			ret[i] = ni();
		return ret;
	}

	long[] nla(int size) throws IOException {
		long[] ret = new long[size];
		for (int i = 0; i < size; i++)
			ret[i] = nl();
		return ret;
	}

	double[] nda(int size) throws IOException {
		double[] ret = new double[size];
		for (int i = 0; i < size; i++)
			ret[i] = nd();
		return ret;
	}

	String nextLine() throws IOException {
		strTok = new StringTokenizer("");
		return in.readLine();
	}

	boolean EOF() throws IOException {
		while (!strTok.hasMoreTokens()) {
			String s = in.readLine();
			if (s == null)
				return true;
			strTok = new StringTokenizer(s);
		}
		return false;
	}

	void printRepeat(String s, int count) {
		for (int i = 0; i < count; i++)
			out.print(s);
	}

	void printArray(int[] array) {
		for (int i = 0; i < array.length; i++) {
			if (i > 0)
				out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}

	void printArray(long[] array) {
		for (int i = 0; i < array.length; i++) {
			if (i > 0)
				out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}

	void printArray(double[] array) {
		for (int i = 0; i < array.length; i++) {
			if (i > 0)
				out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}

	void printArray(double[] array, String spec) {
		for (int i = 0; i < array.length; i++) {
			if (i > 0)
				out.print(' ');
			out.printf(Locale.US, spec, array[i]);
		}
		out.println();
	}

	void printArray(Object[] array) {
		boolean blank = false;
		for (Object x : array) {
			if (blank)
				out.print(' ');
			else
				blank = true;
			out.print(x);
		}
		out.println();
	}

	@SuppressWarnings("rawtypes")
	void printCollection(Collection collection) {
		boolean blank = false;
		for (Object x : collection) {
			if (blank)
				out.print(' ');
			else
				blank = true;
			out.print(x);
		}
		out.println();
	}

	static String memoryStatus() {
		return (Runtime.getRuntime().totalMemory()
				- Runtime.getRuntime().freeMemory() >> 20)
				+ "/" + (Runtime.getRuntime().totalMemory() >> 20) + " MB";
	}
}