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.IOException;
import java.util.InputMismatchException;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.TreeSet;
import java.io.Writer;
import java.math.BigInteger;
import java.io.InputStream;

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

class TaskE {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int m = in.readInt();
        int[][] one = new int[32][n];
        for (int i = 0; i < n; i++) {
            int temp = in.readInt();
            for (int j = 0; j < 20; j++) {
                one[j][i] = ((1<<j)&temp)!=0 ? 1 : 0;
            }
        }

        TreeSet < Interval> set[] = new TreeSet[32];
        for (int i = 0; i < 20; i++) {
            set[i] = new TreeSet<Interval>();
        }

//        System.out.println("doodooliuu");
//        for (int i = 0; i < 20; i++) {
//            for (int j = 0; j < n; j++) {
//                System.out.print(one[i][j] + " ");
//            }
//            System.out.println();
//        }

        for (int i = 0; i < 20; i++) {
            int j = 0;
            while(j < n){
                while(j < n && one[i][j]==0)
                    j++;
                if(j==n)
                    continue;
                int cur = j;
                while(cur < n && one[i][cur]==1)
                    cur++;
                set[i].add(new Interval(j, cur-1));
                j = cur;
            }
        }

//        System.out.println("Yoohooooo");
        long value[] = new long[20];
        for (int i = 0; i < 20; i++) {
            for (Interval interval : set[i]) {
                value[i] += interval.getNum();
            }
        }

//        for (int i = 0; i < 10; i++) {
//            System.out.println("value of " + i + " is " + value[i]);
//        }

        for (int j = 0; j < m; j++) {
            int p = in.readInt(); p--;
            int v = in.readInt();
            long ans = 0;
            for (int i = 0; i < 20; i++) {
                if(one[i][p] != (((1<<i)&v)!=0 ? 1 : 0)) {
                    if(one[i][p] == 1) {
                        boolean bef = false;
                        boolean aft = false;
                        if(p-1 >= 0){
                            if(one[i][p-1] == 1)
                                bef = true;
                        }
                        if(p+1 < n) {
                            if(one[i][p+1] == 1){
                                aft = true;
                            }
                        }

                        Interval interval = new Interval(p, p);
                        Interval interval1 = null;
                        Interval interval2 = null;
                        if(bef && aft) {
                            interval1 = set[i].floor(interval);
                            value[i] -= interval1.getNum();

                            interval2 = new Interval(interval1.x, p-1);
                            set[i].add(interval2);
                            value[i] += interval2.getNum();

                            interval2 = new Interval(p+1, interval1.y);
                            set[i].add(interval2);
                            value[i] += interval2.getNum();

                            set[i].remove(interval1);
                        }
                        if(bef && !aft){
                            interval1 = set[i].floor(interval);
                            value[i] -= interval1.getNum();

                            interval2 = new Interval(interval1.x, p-1);
                            set[i].add(interval2);
                            value[i] += interval2.getNum();

                            set[i].remove(interval1);
                        }
                        if(!bef && aft){
                            interval1 = set[i].ceiling(interval);
                            value[i] -= interval1.getNum();

                            interval2 = new Interval(p+1, interval1.y);
                            set[i].add(interval2);
                            value[i] += interval2.getNum();

                            set[i].remove(interval1);
                        }
                        if(!bef && !aft){
                            value[i] -= interval.getNum();
                            set[i].remove(interval);
                        }
                        one[i][p] = 0;
                    }
                    else {
                        boolean bef = false;
                        boolean aft = false;
                        if(p-1 >= 0){
                            if(one[i][p-1] == 1)
                                bef = true;
                        }
                        if(p+1 < n) {
                            if(one[i][p+1] == 1){
                                aft = true;
                            }
                        }

                        Interval interval = new Interval(p, p);
                        Interval interval1 = null;
                        Interval interval2 = null;
                        int first = p;
                        int last = p;
                        if(bef){
                            interval1 = set[i].lower(interval);
                            first = interval1.x;
                            value[i] -= interval1.getNum();
                            set[i].remove(interval1);
                        }
                        if(aft){
                            interval2 = set[i].higher(interval);
                            last = interval2.y;
                            value[i] -= interval2.getNum();
                            set[i].remove(interval2);
                        }
                        one[i][p] = 1;
                        value[i] += new Interval(first, last).getNum();
                        set[i].add(new Interval(first, last));
                    }
                }
                ans += (long) (1<<i) * value[i];
            }
            out.printLine(ans);
        }

    }
}

class Interval extends Pair{

    public Interval(int xx, int yy) {
        super(xx, yy);
    }

    public long getNum(){
        long t = y-x+1;
        return t*(t+1)/2;
    }

}

class InputReader {
    // this IO reading - writing is provided by Egor Kulikov
    private boolean finished = false;

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int peek() {
        if (numChars == -1)
            return -1;
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                return -1;
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar];
    }

    public int readInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public long readLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public String readString() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuffer res = new StringBuffer();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    public static boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    private String readLine0() {
        StringBuffer buf = new StringBuffer();
        int c = read();
        while (c != '\n' && c != -1) {
            if (c != '\r')
                buf.appendCodePoint(c);
            c = read();
        }
        return buf.toString();
    }

    public String readLine() {
        String s = readLine0();
        while (s.trim().length() == 0)
            s = readLine0();
        return s;
    }

    public String readLine(boolean ignoreEmptyLines) {
        if (ignoreEmptyLines)
            return readLine();
        else
            return readLine0();
    }

    public BigInteger readBigInteger() {
        try {
            return new BigInteger(readString());
        } catch (NumberFormatException e) {
            throw new InputMismatchException();
        }
    }

    public char readCharacter() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        return (char) c;
    }

    public double readDouble() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        double res = 0;
        while (!isSpaceChar(c) && c != '.') {
            if (c == 'e' || c == 'E')
                return res * Math.pow(10, readInt());
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        }
        if (c == '.') {
            c = read();
            double m = 1;
            while (!isSpaceChar(c)) {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, readInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                m /= 10;
                res += (c - '0') * m;
                c = read();
            }
        }
        return res * sgn;
    }

    public boolean isExhausted() {
        int value;
        while (isSpaceChar(value = peek()) && value != -1)
            read();
        return value == -1;
    }

    public String next() {
        return readString();
    }
}

class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(outputStream);
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object...objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0)
                writer.print(' ');
            writer.print(objects[i]);
        }
    }

    public void printLine(Object...objects) {
        print(objects);
        writer.println();
    }

    public void printLine(char[] array) {
        writer.println(array);
    }

    public void printFormat(String format, Object...objects) {
        writer.printf(format, objects);
    }

    public void close() {
        writer.close();
    }

    public void flush() {
        writer.flush();
    }
}

class Pair implements Comparable <Pair>{
    public int x, y;

    public Pair(int xx, int yy){
        x = xx;
        y = yy;
    }

    public Pair add(Pair a){
        return new Pair(x + a.x, y + a.y);
    }

    @Override
    public int compareTo(Pair o) {
        if(x!=o.x)
            return x - o.x;
        return y - o.y;
    }
}