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