← 返回题目列表

Codeforces · 400/E

E. Inna 和二进制逻辑

中文机器翻译题面 查看原题

Inna 厌倦了有关女性逻辑的笑话。所以她开始使用二进制逻辑。

Inna 有一个包含 n 个元素的数组 a1[1], a1[2], ..., a1[n]。 Girl 喜欢训练二元逻辑,所以她做了一个由 n 个阶段组成的练习:在第一个阶段 Inna 写出数组 a1 中的所有数字,在第 i (i ≥ 2) 阶段 Girl 写出数组 ai 的所有元素,该数组由 n - i + 1 个整数组成;数组 ai 的第 k 个整数定义如下:ai[k] = ai - 1[k] AND ai - 1[k + 1]。这里AND是按位二进制逻辑运算。

迪玛决定检查一下伊娜的技能。他要求 Inna 更改数组,执行练习,并说出她在当前练习中写出的所有 $$\frac{n(n+1)}{2}$$ 元素的总和。

帮助Inna回答问题!

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 105) — 数组 a1 的大小和 Dima 问题的数量。下一行包含 n 个整数 a1[1], a1[2], ..., a1[n] (0 ≤ ai ≤ 105) — 初始数组元素。

接下来的 m 行中的每一行都包含两个整数 - Dima 的问题描述。每个问题由两个整数 pi、vi (1 ≤ pi ≤ n; 0 ≤ vi ≤ 105) 组成。对于这道题,Inna 应该使 a1[pi] 等于 vi,然后进行练习。请注意,更改会根据问题保存。

输出

对于每个问题,将 Inna 的答案打印在一行上。

示例

输入 #1

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

输出 #1

6
4
7
12