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

public class E
{
	private final static int Max_Bit = 17;
	private static int [][] nodes;
	private static int size;

	public static void main(String [] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));
		StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

		int n = Integer.parseInt(tokenizer.nextToken());
		int m = Integer.parseInt(tokenizer.nextToken());

		int [] array = new int[n];
		tokenizer = new StringTokenizer(reader.readLine());
		for(int i = 0 ; i < n ; i++)
			array[i] = Integer.parseInt(tokenizer.nextToken());

		size = 1;
		while(size <= n)
			size <<= 1;
		nodes = new int[Max_Bit][size];

		//Node [] root = new Node[Max_Bit];
		//for(int i = 0 ; i < Max_Bit ; i++)
		//	root[i] = make(0, n-1, null, i);

		for(int i = 0 ; i < Max_Bit ; i++)
			for(int j = 0 ; j < n ; j++)
				if(((1<<i) & array[j]) != 0)
					add(i, j+1, 1);

		long sum = 0;
		for(int b = 0 ; b < Max_Bit ; b++)
		{
			int at = 0;
			while(at < n)
			{
				while(at < n && ((1<<b) & array[at]) == 0)
					at++;
				int to = at;
				while(to < n && ((1<<b) & array[to]) != 0)
					to++;

				sum += (1L<<b)*(long)(to-at)*(long)(to-at+1)/2;

				at = to;
			}
		}

		while(m-- > 0)
		{
			tokenizer = new StringTokenizer(reader.readLine());
			int p = Integer.parseInt(tokenizer.nextToken()) - 1;
			int v = Integer.parseInt(tokenizer.nextToken());

			for(int b = 0 ; b < Max_Bit ; b++)
			{
				if(((1<<b) & array[p]) != ((1<<b) & v))
				{
					if(((1<<b) & array[p]) == 0) //0 to 1
					{
						int lb1 = p;
						int ub1 = n;
						while(ub1 - lb1 > 1)
						{
							int mid = (lb1+ub1)/2;
							if(acc(b, mid+1) - acc(b, p) == mid-p)
								lb1 = mid;
							else
								ub1 = mid;
						}

						int lb2 = -1;
						int ub2 = p;
						while(ub2 - lb2 > 1)
						{
							int mid = (lb2 + ub2)/2;
							if(acc(b, p+1) - acc(b, mid) == p-mid)
								ub2 = mid;
							else
								lb2 = mid;
						}

						int st = ub2;
						int en = lb1;

						sum -= (1L<<b)*(long)(en-(p+1)+1)*(long)(en-(p+1)+2)/2;
						sum -= (1L<<b)*(long)(p-1-st+1)*(long)(p-1-st+2)/2;
						sum += (1L<<b)*(long)(en-st+1)*(long)(en-st+2)/2;

						add(b, p+1, 1);
					}
					else //1 to 0
					{
						int lb1 = p;
						int ub1 = n;
						while(ub1 - lb1 > 1)
						{
							int mid = (lb1+ub1)/2;
							if(acc(b, mid+1) - acc(b, p) == mid-p+1)
								lb1 = mid;
							else
								ub1 = mid;
						}

						int lb2 = -1;
						int ub2 = p;
						while(ub2 - lb2 > 1)
						{
							int mid = (lb2 + ub2)/2;
							if(acc(b, p+1) - acc(b, mid) == p-mid+1)
								ub2 = mid;
							else
								lb2 = mid;
						}

						int st = ub2;
						int en = lb1;

						sum -= (1L<<b)*(long)(en-st+1)*(long)(en-st+2)/2;
						sum += (1L<<b)*(long)(p-st)*(long)(p-st+1)/2;
						sum += (1L<<b)*(long)(en-p)*(long)(en-p+1)/2;

						add(b, p+1, -1);
					}
				}

			}
			array[p] = v;

			writer.println(sum);
		}
		writer.flush();
		writer.close();
	}

	public static int acc(int bit, int idx)
	{
		int res = 0;
		while(idx != 0)
		{
			res += nodes[bit][idx];
			idx -= idx&-idx;
		}

		return res;
	}

	public static void add(int bit, int idx, int val)
	{
		while(idx < size)
		{
			nodes[bit][idx] += val;
			idx += idx&-idx;
		}
	}
}