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;

/**
 * @author Don Li
 */
public class InnaBinaryLogic {
    void solve() {
        int n = in.nextInt(), T = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = in.nextInt();
        
        FenwickKth[] fen = new FenwickKth[20];
        for (int i = 0; i < 20; i++) {
            fen[i] = new FenwickKth(n + 2);
            for (int j = 0; j <= n + 1; j++) fen[i].add(j, 1);
        }
        
        long ans = 0;
        for (int i = 0; i < 20; i++) {
            for (int j = 0; j < n; j++) {
                if ((a[j] & (1 << i)) > 0) {
                    fen[i].add(j + 1, -1);
                    ans += get(fen[i], j + 1) << i;
                }
            }
        }
        
        while (T-- > 0) {
            int p = in.nextInt() - 1, v = in.nextInt();
            for (int i = 0; i < 20; i++) {
                if ((v & (1 << i)) != (a[p] & (1 << i))) {
                    if ((v & (1 << i)) > 0) {
                        fen[i].add(p + 1, -1);
                        ans += get(fen[i], p + 1) << i;
                    } else {
                        ans -= get(fen[i], p + 1) << i;
                        fen[i].add(p + 1, 1);
                    }
                }
            }
            a[p] = v;
            out.println(ans);
        }
    }
    
    long get(FenwickKth fen, int i) {
        int cnt = fen.sum(i);
        int p = fen.getKth(cnt), q = fen.getKth(cnt + 1);
        return (long) (i - p) * (q - i);
    }
    
    static class FenwickKth {
        int[] a;
        
        public FenwickKth(int n) {
            a = new int[Integer.highestOneBit(n) << 1];
        }
        
        public void add(int x, int delta) {
            for (int i = x; i < a.length; i |= i + 1) {
                a[i] += delta;
            }
        }
        
        public int sum(int x) {
            int ret = 0;
            for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
                ret += a[i];
            }
            return ret;
        }
        
        public int getKth(int k) {
            int l = 0;
            int r = a.length;
            while (l < r - 1) {
                int mid = l + r >> 1;
                if (a[mid - 1] >= k) {
                    r = mid;
                } else {
                    k -= a[mid - 1];
                    l = mid;
                }
            }
            return l;
        }
        
    }
    
    public static void main(String[] args) {
        in = new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(System.out);
        new InnaBinaryLogic().solve();
        out.close();
    }
    
    static FastScanner in;
    static PrintWriter out;
    
    static class FastScanner {
        BufferedReader in;
        StringTokenizer st;
        
        public FastScanner(BufferedReader in) {
            this.in = in;
        }
        
        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        public int nextInt() {
            return Integer.parseInt(nextToken());
        }
        
        public long nextLong() {
            return Long.parseLong(nextToken());
        }
        
        public double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}