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.Reader;
import java.util.InputMismatchException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.io.IOException;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Niyaz Nigmatullin
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastScanner in = new FastScanner(inputStream);
		FastPrinter out = new FastPrinter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    public void solve(int testNumber, FastScanner in, FastPrinter out) {
        int n = in.nextInt();
        int m = in.nextInt();
        FenwickKth[] set = new FenwickKth[17];
        for (int i = 0; i < set.length; i++) set[i] = new FenwickKth(n + 2);
        for (FenwickKth e : set) {
            for (int i = 0; i <= n + 1; i++) e.add(i, 1);
        }
        long ans = 0;
        for (int i = 0; i < n; i++) {
            int x = in.nextInt();
            for (int bit = 0; bit < set.length; bit++) {
                if (((x >> bit) & 1) == 1) {
                    set[bit].add(i + 1, -1);
                    ans += get(set[bit], i) << bit;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            int x = in.nextInt() - 1;
            int y = in.nextInt();
            for (int bit = 0; bit < set.length; bit++) {
                if ((set[bit].getSum(x + 1, x + 2) == 1) != (((y >> bit) & 1) == 0)) {
                    if (((y >> bit) & 1) == 1) {
                        set[bit].add(x + 1, -1);
                        ans += get(set[bit], x) << bit;
                    } else {
                        ans -= get(set[bit], x) << bit;
                        set[bit].add(x + 1, 1);
                    }
                }
            }
            out.println(ans);
        }
    }

    static long get(FenwickKth set, Integer i) {
        i++;
        int sum = set.getSum(i);
        int prev = set.getKth(sum);
        int next = set.getKth(sum + 1);
        return (long) (i - prev) * (next - i);
    }
}

class FastScanner extends BufferedReader {

    public FastScanner(InputStream is) {
        super(new InputStreamReader(is));
    }

    public int read() {
        try {
            int ret = super.read();
//            if (isEOF && ret < 0) {
//                throw new InputMismatchException();
//            }
//            isEOF = ret == -1;
            return ret;
        } catch (IOException e) {
            throw new InputMismatchException();
        }
    }

    static boolean isWhiteSpace(int c) {
        return c >= 0 && c <= 32;
    }

    public int nextInt() {
        int c = read();
        while (isWhiteSpace(c)) {
            c = read();
        }
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int ret = 0;
        while (c >= 0 && !isWhiteSpace(c)) {
            if (c < '0' || c > '9') {
                throw new NumberFormatException("digit expected " + (char) c
                        + " found");
            }
            ret = ret * 10 + c - '0';
            c = read();
        }
        return ret * sgn;
    }

    public String readLine() {
        try {
            return super.readLine();
        } catch (IOException e) {
            return null;
        }
    }

}

class FastPrinter extends PrintWriter {

    public FastPrinter(OutputStream out) {
        super(out);
    }


}

class FenwickKth {
    int[] a;

    public FenwickKth(int n) {
        a = new int[Integer.highestOneBit(n) << 1];
    }

    public void add(int x, int y) {
        for (int i = x; i < a.length; i |= i + 1) {
            a[i] += y;
        }
    }

    public int getSum(int x) {
        if (x >= a.length) x = a.length - 1;
        int ret = 0;
        for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
            ret += a[i];
        }
        return ret;
    }

    public int getSum(int l, int r) {
        return getSum(r - 1) - getSum(l - 1);
    }

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

}