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) throws IOException {

        PrintWriter pf = new PrintWriter(System.out);
        Fastget sf = new Fastget();
        SegmentTree[] sgt = new SegmentTree[17];
        sf.accept();
        Iterator<int[]> iterator = sf.iterator();

        int[] line = iterator.next();
        int n = line[0], m = line[1];

        int[] a = new int[n + 5];
        for (int i = 0; i < 17; ++i) {
            sgt[i] = new SegmentTree(n * 2 + 5);
        }

        int[] line2 = iterator.next();
        for (int i = 1; i <= n; ++i) {
            a[i] = line2[i - 1];
            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[] tem = iterator.next();
            int c = tem[0];
            int x = tem[1];
            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 implements Iterable<int[]> {
    private List<int[]> input;

    public Fastget() {

    }

    public void accept() throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        input = new LinkedList<int[]>();
        boolean hasInput = false;
        String s =  null;
        while ( (s=in.readLine())!= null||!hasInput ) {
            if (s != null) {
                String[] tokens = s.split(" ");
                int[] datas = new int[tokens.length];
                for (int i = 0; i < tokens.length; i++) {
                    datas[i] = Integer.valueOf(tokens[i]);
                }
                input.add(datas);
                hasInput = true;
                //break;
            }
        }
    }

    @Override
    public Iterator<int[]> iterator() {
        return input.iterator();
    }

    //
    // 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;
}