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


public class InnaandBinaryLogic {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
        int arr[] = new int [n+1];
        TreeSet<Integer> [] bit = new TreeSet [18];
        for(int i =0;i<bit.length;i++){
            bit[i] = new TreeSet<Integer>();
            bit[i].add(0);
            bit[i].add(n+1);
        }
        long res = 0;
        st = new StringTokenizer(in.readLine());
        for(int i = 1;i<arr.length;i++){
            arr[i] = Integer.parseInt(st.nextToken());
            for(int j = 0;j<bit.length;j++){
                if((arr[i]&(1<<j))==0){
                    bit[j].add(i);
                }
            }
        }
        for(int i = 0;i<bit.length;i++){
            long cnt = 0;
            for(int j = 1;j<=n;j++){
                if((arr[j]&(1<<i))!=0){
                    cnt++;
                }
                else{
                    res+=(cnt*(cnt+1)/2)*(1L<<i);
                    cnt = 0;
                }
            }
            res+=(cnt*(cnt+1)/2)*(1L<<i);
        }
        for(int i = 0;i<q;i++){
            st = new StringTokenizer(in.readLine());
            int p = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            for(int j = 0;j<bit.length;j++){
                if((arr[p]&(1<<j))!=0){
                    long begin = bit[j].floor(p);
                    long end = bit[j].ceiling(p+1);
                    long len = end - begin-1;
                    res-= (len*(len+1)/2)*(1L<<j);
                    len = p-begin-1;
                    res+= (len*(len+1)/2)*(1L<<j);
                    len = end-p-1;
                    res+= (len*(len+1)/2)*(1L<<j);
                    bit[j].add(p);
                }
            }
            for(int j = 0;j<bit.length;j++){
                if((v&(1<<j))!=0){
                    long begin = bit[j].floor(p-1);
                    long end = bit[j].ceiling(p+1);
                    long len = end - begin-1;
                    res+= (len*(len+1)/2)*(1L<<j);
                    len = p-begin-1;
                    res-= (len*(len+1)/2)*(1L<<j);
                    len = end-p-1;
                    res-= (len*(len+1)/2)*(1L<<j);
                    bit[j].remove(p);
                }
            }
            out.println(res);
            arr[p] = v;
        }
        in.close();
        out.close();
    }
}