Inna and Binary Logic

题意翻译

Inna 有一个一个长度为 $n$ 的数列 $a_1 [1],a_1 [2],\dots,a_1 [n]$。 她会进行如下操作，分为 $n$ 个阶段： 在第一阶段，Inna 从数组 $a_1$中写出所有数字，在第 $i$ 个 $(i \ge 2)$ 阶段 Inna 会写出数组的所有元素 $a_i$ ，由 $n - i + 1$ 个整数组成; 数组 $a_i$ 的第 $k$ 个数定义如下：$a_{i} [k] = a_{i-1} [k]\ \mathrm{AND}\ a_{i-1} [k + 1]$ 。 这里 $\mathrm{AND}$ 是二进制的逐位与运算。 Dima 决定检验 Inna 的技能。 他要求 Inna 改变阵列，进行练习并说出她在当前练习中写出的所有元素的总和，即： $\sum_{i=1}^n \sum_{j=1}^{n-i+1} a_i[j]$ 请帮助Inna回答问题！

题目描述

Inna is fed up with jokes about female logic. So she started using binary logic instead. Inna has an array of $ n $ elements $ a_{1}[1],a_{1}[2],...,a_{1}[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 $ a_{1} $ , on the $ i $ -th $ (i>=2) $ stage girl writes all elements of array $ a_{i} $ , which consists of $ n-i+1 $ integers; the $ k $ -th integer of array $ a_{i} $ is defined as follows: $ a_{i}[k]=a_{i-1}[k] AND a_{i-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  elements she wrote out during the current exercise. Help Inna to answer the questions!

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ $ (1<=n,m<=10^{5}) $ — size of array $ a_{1} $ and number of Dima's questions. Next line contains $ n $ integers $ a_{1}[1],a_{1}[2],...,a_{1}[n] $ $ (0<=a_{i}<=10^{5}) $ — initial array elements. Each of next $ m $ lines contains two integers — Dima's question description. Each question consists of two integers $ p_{i},v_{i} $ $ (1<=p_{i}<=n; 0<=v_{i}<=10^{5}) $ . For this question Inna should make $ a_{1}[p_{i}] $ equals $ v_{i} $ , and then perform the exercise. Please, note that changes are saved from question to question.

输出格式

For each question print Inna's answer on a single line.

输入输出样例

输入样例 #1

3 4
1 1 1
1 1
2 2
3 2
1 2

输出样例 #1

6
4
7
12