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.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class ProblemE {

    static class BIT {
         int N;
         long[] data;
         BIT(int n) {
              N = n;
              data = new long[n+1];
         }
        
         long sum(int i) {
              long s = 0;
              while (i > 0) {
                   s += data[i];
                   i -= i & (-i);
              }
              return s;
         }
        
         long range(int i, int j) {
              return sum(j) - sum(i-1);
         }
        
         void add(int i, long x) {
              while (i <= N) {
                   data[i] += x;
                   i += i & (-i);
              }
         }
         
         // find rightmost non-zero position less or equal x
         int beforeNonZeroPosition(int x) {
        	 long u = sum(x-1);
        	 return findMostLeftPositionValueOf(u)+1;
         }
         
         // find leftmost non-zero position more or equal x
         int afterNonZeroPosition(int x) {
        	 long u = sum(x);
        	 return findMostRightPositionValueOf(u);
         }
         
         // find position　at most right that have a[i] == value
         int findMostRightPositionValueOf(long value) {
        	 int i = 0;
        	 int n = data.length;
        	 for (int b = Integer.highestOneBit(n) ; b != 0 && i < n ; b >>= 1) {
        		 if (i + b < n) {
        			 int t = i + b;
        			 if (value >= data[t]) {
        				 i = t;
        				 value -= data[t];
        			 }
        		 }
        	 }
        	 return i;
         }
         
         // find position at most left that have a[i] == value
         int findMostLeftPositionValueOf(long value) {
        	 if (value <= 0) {
        		 return 0;
        	 }
        	 // <most left> = <most right at previous value> + 1
        	 return findMostRightPositionValueOf(value-1)+1;
         }

    }

	public static void main(String[] args) throws IOException {
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);

		int n = in.nextInt();
		int m = in.nextInt();
		int[] a = new int[n];
		for (int i = 0 ; i < n ; i++) {
			a[i] = in.nextInt();
		}
		int[][] queries = new int[m][2];
		for (int i = 0 ; i < m ; i++) {
			queries[i][0] = in.nextInt();
			queries[i][1] = in.nextInt();
		}
		
		BIT[] bit = new BIT[17];
		for (int b = 0 ; b < 17 ; b++) {
			bit[b] = new BIT(n);
			for (int i = 0 ; i < n ; i++) {
				if (((a[i] >>> b) & 1) == 0) {
					bit[b].add(i+1, 1);
				}
			}
		}
		
		// debug(bit[0].range(1, 9));
		// debug(bit[0].beforeNonZeroPosition(5));
		// debug(bit[0].afterNonZeroPosition(5));
		
		
		long[] answer = new long[m+1];
		for (int b = 0 ; b < 17 ; b++) {
			long cnt = 0;
			for (int i = 0 ; i < n ; i++) {
				if (((a[i] >>> b) & 1) == 1) {
					cnt++;
				} else {
					answer[0] += ((cnt * (cnt + 1)) / 2) << b;
					cnt = 0;
				}
			}
			answer[0] += ((cnt * (cnt + 1)) / 2) << b;
		}
		
		
		for (int i = 0 ; i < m ; i++) {
			for (int b = 0 ; b < 17 ; b++) {
				int fr = (a[queries[i][0]-1] >>> b) & 1; 
				int to = ((queries[i][1] >>> b) & 1);
				if (fr != to) {
					int before = bit[b].beforeNonZeroPosition(queries[i][0]);
					int after = bit[b].afterNonZeroPosition(queries[i][0]);

					if (to == 0) {
						// divide
						long ones = (after - before) + 1;
						long left = queries[i][0] - before;
						long right = after - queries[i][0];
						answer[i] -= (ones * (ones + 1) / 2) << b;
						answer[i] += (left * (left + 1) / 2) << b;
						answer[i] += (right * (right + 1) / 2) << b;
						bit[b].add(queries[i][0], 1);
					} else {
						// connect
						long left = queries[i][0] - before;
						long right = after - queries[i][0];
						long ones = left + right + 1;
						answer[i] += (ones * (ones + 1) / 2) << b;
						answer[i] -= (left * (left + 1) / 2) << b;
						answer[i] -= (right * (right + 1) / 2) << b;
						bit[b].add(queries[i][0], -1);
					}
				}
			}
			a[queries[i][0]-1] = queries[i][1];
			answer[i+1] = answer[i];
		}
			
		for (int i = 0 ; i < m ; i++) {
			out.println(answer[i]);
		}
		
		out.flush();
	}

	public static void debug(Object... o) {
		System.err.println(Arrays.deepToString(o));
	}

	static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int next() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = next();
			while (isSpaceChar(c))
				c = next();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = next();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = next();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
}