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.DataInputStream;
import java.io.InputStream;
import java.io.PrintWriter;

public class InnaAndBinaryLogic {

  
  public static void main(String[] args) throws Exception {
    
    Parserdoubtaaa in = new Parserdoubtaaa(System.in);
    PrintWriter out = new PrintWriter(System.out);
    
    n = in.nextInt() + 1;
    int m = in.nextInt();
    
    res = 0;
    tree = new long[bits][n];
    
    for (int i = 1; i < n; i++) {
      int a = in.nextInt();
      for (int j = 0; j < bits; j++) {
        int bit = (((1 << j) & a) > 0)?1:0;
        doit(i, bit, tree[j], 1L << j);
      }
    }
    
    for (int i = 0; i < m; i++) {
      int idx = in.nextInt();
      int a = in.nextInt();
      for (int j = 0; j < bits; j++) {
        int bit = (((1 << j) & a) > 0)?1:0;
        doit(idx, bit, tree[j], 1L << j);
      }
      out.println(res);
    }
    
    out.close();
  }
  

  static int bits = 20;
  static long tree[][];
  static int n;
  static long res;
  
  private static void update(int idx, int value, long[] tree) {
    while(idx < tree.length) {
      tree[idx] += value;
      idx += idx & -idx;
    }
  }
  
  private static long read(int idx, long tree[]) {
    long sum = 0;
    while(idx > 0) {
      sum += tree[idx];
      idx -= idx & -idx;
    }
    return sum;
  }
  
  
  private static void doit(int idx, int nextBit, long[] tree, long bitValue) {
    
    long currentBit = read(idx, tree) - read(idx - 1, tree);
    
    if(currentBit == 0 && nextBit == 1) {
  
      // left size     
      long size1 = 0;
      
      int left = 0;
      int right = n;
      while(left <= right) {
        int mid = (left + right) >> 1;
        
        int idxLeft = idx - mid;
        if(idxLeft <= 0) {
          right = mid - 1;
        }
        else {
          long s = read(idx, tree) - read(idxLeft-1, tree);
          if(s == idx - idxLeft) {
            size1 = mid;
            left = mid + 1;
          }
          else {
            right = mid - 1;
          }
        }
      }
      
      // right size
      
      long size2 = 0;
      left = 0;
      right = n;
      while(left <= right) {
        int mid = (left + right) >> 1;
     
        int idxRight = idx + mid;
        if(idxRight >= n){
          right = mid - 1;
        }
        else {
          long s = read(idxRight, tree) - read(idx, tree);
          if(s == idxRight - idx){
            size2 = mid;
            left = mid + 1;
          }
          else {
            right = mid - 1;
          }
        }
      }
      
      res -= bitValue*size1*(size1+1)/2;
      res -= bitValue*size2*(size2+1)/2;
      
      long len = size1 + size2 + 1;
      res += bitValue*len*(len+1)/2;
      
      update(idx, 1, tree);
    }
    else if(currentBit == 1 && nextBit == 0){
      
      // left size
      long size1 = 0;
      int left = 0;
      int right = n;
      while(left <= right) {
        int mid = (left + right) >> 1;
        
        int idxLeft = idx - mid;
        if(idxLeft <= 0) {
          right = mid - 1;
        }
        else {
          long s = read(idx, tree) - read(idxLeft-1, tree);
          if(s == idx - idxLeft + 1) {
            size1 = mid;
            left = mid + 1;
          }
          else {
            right = mid - 1;
          }
        }
      }
      
      // right size
      long size2 = 0;
      left = 0;
      right = n;
      while(left <= right) {
        int mid = (left + right) >> 1;
        
        int idxRight = idx + mid;
        if(idxRight >= n){
          right = mid - 1;
        }
        else {
          long s = read(idxRight, tree) - read(idx-1, tree);
          if(s == idxRight - idx + 1) {
            size2 = mid;
            left = mid + 1;
          }
          else {
            right = mid - 1;
          }
        }
      }
      
      long len = size1 + size2 + 1;
      
      res -= bitValue*len*(len+1)/2;
      
      res += bitValue*size1*(size1+1)/2;
      res += bitValue*size2*(size2+1)/2;
      
      update(idx, -1, tree);
      
    }
  }

}


class Parserdoubtaaa
{
   final private int BUFFER_SIZE = 1 << 17;
 
   private DataInputStream din;
   private byte[] buffer;
   private int bufferPointer, bytesRead;
 
   public Parserdoubtaaa(InputStream in)
   {
      din = new DataInputStream(in);
      buffer = new byte[BUFFER_SIZE];
      bufferPointer = bytesRead = 0;
   }
   public String nextString() throws Exception
   {
       StringBuffer sb=new StringBuffer("");
       byte c = read();
       while (c <= ' ') c = read();
       do
       {
           sb.append((char)c);
           c=read();
       }while(c>' ');
       return sb.toString();
   }
   public char nextChar() throws Exception
   {
       byte c=read();
       while(c<=' ') c= read();
       return (char)c;
   }
   public int nextInt() throws Exception
   {
      int ret = 0;
      byte c = read();
      while (c <= ' ') c = read();
      boolean neg = c == '-';
      if (neg) c = read();
      do
      {
          ret = ret * 10 + c - '0';
         c = read();
      } while (c > ' ');
      if (neg) return -ret;
      return ret;
   }
   public long nextLong() throws Exception
   {
      long ret = 0;
      byte c = read();
      while (c <= ' ') c = read();
      boolean neg = c == '-';
      if (neg) c = read();
      do
      {
          ret = ret * 10 + c - '0';
         c = read();
      } while (c > ' ');
      if (neg) return -ret;
      return ret;
   }
   private void fillBuffer() throws Exception
   {
      bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
      if (bytesRead == -1) buffer[0] = -1;
   }
 
   private byte read() throws Exception
   {
      if (bufferPointer == bytesRead) fillBuffer();
      return buffer[bufferPointer++];
   }
}