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 Main {
    
    public static void main(String[] args) {
        
        PrintWriter pf = new PrintWriter(System.out);
        fastget sf = new fastget();
        segmenttree[] sgt = new segmenttree[17]; 
        int n = sf.nextInt(),m = sf.nextInt();
        int[] a = new int[n+5];
        for(int i=0;i<17;++i)
            sgt[i] = new segmenttree(n*2+5);
        for(int i=1;i<=n;++i) {
            a[i] = sf.nextInt();
            int x = a[i];
            for(int j=0;j<17;++j) {
                if((x&1)==1) sgt[j].update(1,n,i,x&1);
                x>>=1;
            }
        }
        for(int i=1;i<=m;++i) {
            int c = sf.nextInt();
            int x = sf.nextInt();
            long ans = 0;
            for(int j=0;j<17;++j) {
                if((a[c]&(1<<j))!=(x&(1<<j))) sgt[j].update(1,n,c,(x>>j)&1);
                ans+=sgt[j].getss(1,n)*(1<<j);
            }
            a[c]=x;
            pf.println(ans);
        }
        pf.close();
    }
}

class fastget {
    
    private BufferedReader in;
    private StringTokenizer st;
    
    public fastget() {
        in = new BufferedReader(new InputStreamReader(System.in));
    }
    
    private String next() {
        while (st==null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(in.readLine());
            } catch (Exception e) {}
        }
        return st.nextToken(); 
    }
    
    public int nextInt() {
        return Integer.parseInt(next());
    }
    
    public long nextLong() {
        return Long.parseLong(next());
    }
    
    public double nextDouble() {
        return Double.parseDouble(next());
    }
    
}

class segmenttree {
    
    public segmenttree(int n){
        ls = new int[n];
        rs = new int[n];
        ss = new long[n];
    }
    
    public int id(int l,int r) {
        return l+r | (l!=r?1:0);
    }
    
    public void update(int l,int r,int i,int x) {
        int rt = id(l,r);
        if(l==r) {
            if(x==1) ss[rt]=ls[rt]=rs[rt]=1;
            else ss[rt]=ls[rt]=rs[rt]=0;
            return;
        }
        int mid=l+r>>1;
        if(i<=mid) update(l,mid,i,x);
        else update(mid+1,r,i,x);
        int rtl = id(l,mid),rtr = id(mid+1,r);
        ss[rt] = ss[rtl]+ss[rtr]+(rs[rtl]+ls[rtr]+1L)*(rs[rtl]+ls[rtr])/2;
        ss[rt] -= (rs[rtl]+1L)*rs[rtl]/2;
        ss[rt] -= (ls[rtr]+1L)*ls[rtr]/2;
        if(ls[rtl]==mid-l+1) ls[rt] = ls[rtl]+ls[rtr];
        else ls[rt] = ls[rtl];
        if(rs[rtr]==r-mid) rs[rt] = rs[rtr]+rs[rtl];
        else rs[rt] = rs[rtr];
    }
    
    public long getss(int l,int r) {
        return ss[id(l,r)];
    }
    
    private int[] ls;
    private int[] rs;
    private long[] ss;
}