CF400E.Inna and Binary Logic

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!

因娜受够了关于女性逻辑的玩笑，于是她开始使用二进制逻辑。

因娜有一个包含 $n$ 个元素的数组 $a_1[1],\ a_1[2],\ \dots,\ a_1[n]$。这位姑娘喜欢通过二进制逻辑训练自己，因此她进行一项包含 $n$ 个阶段的练习：在第 $1$ 阶段，因娜写出数组 $a_1$ 中的所有数；在第 $i$ 阶段（其中 $i \geq 2$），她写出数组 $a_i$ 的所有元素，该数组 $a_i$ 包含 $n - i + 1$ 个整数；数组 $a_i$ 的第 $k$ 个整数定义如下：

$$a_i[k] = a_{i-1}[k]\ \text{AND}\ a_{i-1}[k+1].$$

此处 AND 表示按位二进制逻辑与运算。

迪马决定检验因娜的技能。他要求因娜修改数组，执行上述练习，并报告她在本次练习中所写出的所有 个元素之和。

请帮助因娜回答这些问题！

The first line contains two integers n and m (1 ≤ n, m ≤ 105) — 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 ≤ 105) — 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 ≤ 105). 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.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 10^5$）——分别表示数组 $a_1$ 的大小以及 Dima 提出的问题数量。
下一行包含 $n$ 个整数 $a_1[1],\ a_1[2],\ \dots,\ a_1[n]$（$0 \leq a_i \leq 10^5$）——初始数组的元素。

接下来的 $m$ 行，每行包含两个整数，描述 Dima 的一个问题。每个问题由两个整数 $p_i,\ v_i$（$1 \leq p_i \leq n$；$0 \leq v_i \leq 10^5$）组成。对于该问题，Inna 需将 $a_1[p_i]$ 修改为 $v_i$，然后执行练习。请注意，每次修改会保留至后续问题。

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

对于每个问题，在一行中输出因娜的答案。