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;
import java.util.*;


public class ProblemAA {

  
  public static void main(String args[]) throws Exception {
    
    Parserdoubt1223 in = new Parserdoubt1223(System.in);
    PrintWriter out = new PrintWriter(System.out);
    
    n = in.nextInt();
    m = in.nextInt();
    a = new long [n+1];
    
    for (int i = 0; i < n; i++) {
      a[i+1] = in.nextInt();
    }
    
    
    tree = new long[bits][n+1];
    for (int i = 0; i < bits; i++) {
      for (int j = 1; j < a.length; j++) {
        if(((1 << i)&a[j]) > 0) {
          update(j, 1, tree[i]);
        }
      }
    }
    
    long res = 0;
    
    for (int i = 0; i < bits; i++) {
      for (int j = 1; j < a.length; j++) {
        if(((1 << i) & a[j]) > 0) {
          
          
          int left = 0;
          int right = a.length;
          
          long ans = 0;
          
          while(left <= right) {
            int mid = (left + right) >> 1;
          
          
            int idx1 = j;
            int idx2 = j + mid;
            
            if(idx2 >= a.length) {
              right = mid - 1;
              continue;
            }
            else {
              long s = read(idx2, tree[i]) - read(idx1, tree[i]);
              
              if(s == mid) {
                ans = mid;
                left = mid + 1;
              }
              else {
                right = mid - 1;
              }
            }
          }
          
          long idx1 = j;
          long idx2 = j + ans;
          
          res += (1<<i)*(ans+1);
          
        }
      }
    }
    
//    System.out.println(res);
//    System.out.println("AAA");
    for (int i = 0; i < m; i++) {
//      System.out.println("##########");
      int idx = in.nextInt();
      long value = in.nextInt();
      
      for (int k = 0; k < bits; k++) {
//        long bit1 = ((1 << k) * read(idx, tree[k]) - read(idx-1, tree[k]));
        long bit1 = ((1 << k) & a[idx]);
        long bit2 = ((1 << k) & value);
//        System.out.println(k + " " + bit1 + " " + bit2 + " " + a[idx] + " " + value);
        if(bit1 == 0 && bit2 > 0) {
           
          long ans1 = 0;
          int left = 0;
          int right = a.length;
          while(left <= right) {
            int mid = (left + right) >> 1;
            int i1 = idx - mid;
            int i2 = idx;
            
            if(i1 <= 0){
              right = mid - 1;
              continue;
            }
            
            long s = read(i2, tree[k]) - read(i1 - 1, tree[k]);
            
            if(s == i2 - i1){
              ans1 = mid;
              left = mid + 1;
            }
            else {
              right = mid - 1;
            }
          }
          
          long ans2 = 0;
          left = 0;
          right = a.length;
          while(left <= right) {
            int mid = (left + right) >> 1;
            int i1 = idx;
            int i2 = idx + mid;
            if(i2 >= a.length){
              right = mid - 1;
              continue;
            }
            
            long s = read(i2, tree[k]) - read(i1 - 1, tree[k]);
            if(s == i2 - i1) {
              ans2 = mid;
              left = mid + 1;
            }
            else {
              right = mid - 1;
            }
          }
          
          
          res -= (1<<k) * ans1 * (ans1 + 1)/2;
          res -= (1<<k) * ans2 * (ans2 + 1)/2;
          
          update(idx, 1, tree[k]);
          
          long a = ans1 + ans2 + 1;
          res += (1<<k) * a * (a + 1)/2;
          
//          System.out.println("0-1   " + ans1 + " " +  ans2 + "   res: " + res);
          
        }
        else if(bit1 > 0 && bit2 == 0) {
          
          int ans1 = 0;
          int left = 0;
          int right = a.length;
          while(left <= right) {
            int mid = (left + right) >> 1;
            int i1 = idx - mid;
            int i2 = idx;
            
            if(i1 <= 0){
              right = mid - 1;
              continue;
            }
            
            long s = read(i2, tree[k]) - read(i1 - 1, tree[k]);
            
            if(s == i2 - i1 + 1){
              ans1 = mid;
              left = mid + 1;
            }
            else {
              right = mid - 1;
            }
          }
          
          int ans2 = 0;
          left = 0;
          right = a.length;
          while(left <= right) {
            int mid = (left + right) >> 1;
            int i1 = idx;
            int i2 = idx + mid;
            if(i2 >= a.length){
              right = mid - 1;
              continue;
            }
            
            long s = read(i2, tree[k]) - read(i1 - 1, tree[k]);
            if(s == i2 - i1 + 1) {
              ans2 = mid;
              left = mid + 1;
            }
            else {
              right = mid - 1;
            }
          }
          
          long len = ans1 + ans2 + 1;
//          System.out.println("################## START");
//          for (int j = 1; j < tree[k].length; j++) {
//            System.out.println(read(j, tree[k]));
//          }
//          System.out.println("Q: " + idx + " " + value);
          res -= (1 << k) * len * (len + 1)/2;
          
          long a1 = ans1;
          long a2 = ans2;
          res += (1 << k) * a1 * (a1 + 1)/2;
          res += (1 << k) * a2 * (a2 + 1)/2;
          
          update(idx, -1, tree[k]);
          
//          System.out.println("1-0   " + ans1 + " " + ans2 + "   res: " + res);
        }
        
      }
      a[idx] = value;
      
      out.println(res);
    }
    
    
    out.close();
  }
  
  static int n;
  static int m;
  static long a[];
  
  static int bits = 20;
  static long tree[][];
  
  static void update(int idx, int value, long tree[]) {
    while(idx < tree.length) {
      tree[idx] += value;
      idx += idx & -idx;
    }
  }
  
  static long read(int idx, long tree[]) {
    long sum = 0;
    while(idx > 0) {
//      System.out.println(tree.length);
      sum += tree[idx];
      idx -= idx & -idx;
    }
    return sum;
  }
}


class Parserdoubt1223
{
   final private int BUFFER_SIZE = 1 << 17;
 
   private DataInputStream din;
   private byte[] buffer;
   private int bufferPointer, bytesRead;
 
   public Parserdoubt1223(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++];
   }
}