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:
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
What do you think? What do you think?
1st on Billboard, what do you think of it
Next is a Grammy, what do you think of it
However you think, I’m sorry, but shit, I have no fcking interest
*******************************
I'm standing on top of my Monopoly board
That means I'm on top of my game and it don't stop
til my hip don't hop anymore
https://www.a2oj.com/Ladder16.html
*******************************
300iq as writer = Sad!
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x400E
   {
      public static void main(String hi[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         int Q = Integer.parseInt(st.nextToken());
         StringBuilder sb = new StringBuilder();
         int[] arr = new int[N+1];
         st = new StringTokenizer(infile.readLine());
         for(int i=0; i < N; i++)
            arr[i+1] = Integer.parseInt(st.nextToken());
         FenwickTree[] bits = new FenwickTree[17];
         for(int i=0; i < 17; i++)
            bits[i] = new FenwickTree(N+3);
         long[] vals = new long[17];
         for(int b=0; b < 17; b++)
         {
            ArrayList<Integer> ls = new ArrayList<Integer>();
            ls.add(69120);
            for(int i=1; i <= N; i++)
            {
               int tag = Math.min(1, arr[i]&(1<<b));
               bits[b].add(i, tag);
               ls.add(tag);
            }
            int tag = ls.get(1);
            int size = 1;
            for(int i=2; i <= N; i++)
            {
               if(tag != ls.get(i))
               {
                  if(tag == 1)
                     vals[b] += (long)size*(size+1)/2;
                  size = 1;
               }
               else
                  size++;
               tag = ls.get(i);
            }
            if(tag == 1)
               vals[b] += (long)size*(size+1)/2;
         }
         while(Q-->0)
         {
            st = new StringTokenizer(infile.readLine());
            int dex = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());
            if(N == 1)
            {
               sb.append(val+"\n");
               continue;
            }
            for(int b=0; b < 17; b++)
            {
               FenwickTree fft = bits[b];
               int tag = Math.min(1, val&(1<<b));
               if(tag == fft.find(dex, dex))
                  continue;
               if(dex == 1)
               {
                  int right = findRight(fft, N, dex);
                  if(tag == 1)
                  {
                     vals[b] -= (long)(right-1)*right/2;
                     vals[b] += (long)right*(right+1)/2;
                  }
                  else
                  {
                     vals[b] += (long)(right-1)*right/2;
                     vals[b] -= (long)right*(right+1)/2;
                  }
               }
               else if(dex < N)
               {
                  int left = findLeft(fft, N, dex);
                  int right = findRight(fft, N, dex);
                  long bleft = dex-left;
                  long bright = right-dex;
                  if(tag == 1) //join
                  {
                     vals[b] -= bleft*(bleft+1)/2;
                     vals[b] -= bright*(bright+1)/2;
                     vals[b] += (bleft+bright+1)*(bleft+bright+2)/2;
                  }
                  else //split
                  {
                     vals[b] += bleft*(bleft+1)/2;
                     vals[b] += bright*(bright+1)/2;
                     vals[b] -= (bleft+bright+1)*(bleft+bright+2)/2;
                  }
               }
               else
               {
                  int left = findLeft(fft, N, dex);
                  long block = dex-left;
                  if(tag == 1)
                  {
                     vals[b] -= block*(block+1)/2;
                     vals[b] += (block+1)*(block+2)/2;
                  }
                  else
                  {
                     vals[b] += block*(block+1)/2;
                     vals[b] -= (block+1)*(block+2)/2;
                  }
               }
               if(tag == 0)
                  fft.add(dex, -1);
               else
                  fft.add(dex, 1);
            }
            long res = 0L;
            for(int b=0; b < 17; b++)
               res += vals[b]*(1<<b);
            sb.append(res+"\n");
         }
         System.out.print(sb);
      }
      public static int findLeft(FenwickTree bit, int N, int dex)
      {
         int low = 1;
         int high = dex-1;
         if(bit.find(high, high) == 0)
            return dex;
         while(low != high)
         {
            int mid = (low+high)/2;
            if(bit.find(mid, dex-1) == dex-1-mid+1)
               high = mid;
            else
               low = mid+1;
         }
         return low;
      }
      public static int findRight(FenwickTree bit, int N, int dex)
      {
         int low = dex+1;
         int high = N;
         if(bit.find(low, low) == 0)
            return dex;
         while(low != high)
         {
            int mid = (low+high+1)/2;
            if(bit.find(dex+1, mid) == mid-dex)
               low = mid;
            else
               high = mid-1;
         }
         return low;
      }
   }
   class FenwickTree
   {
      //1 indexed
      public int[] tree;
      public int size;
      
      public FenwickTree(int size)
      {
         this.size = size;
         tree = new int[size+5];
      }
      public void add(int i, int v)
      {
         while(i <= size)
         {
            tree[i] += v;
            i += i&-i;
         }
      }
      public int find(int i)
      {
         int res = 0;
         while(i >= 1)
         {
            res += tree[i];
            i -= i&-i;
         }
         return res;
      }
      public int find(int l, int r)
      {
         return find(r)-find(l-1);
      }
   }