Comet OJ

C0655 [BJWC2008]序列

内存限制：256 MB 时间限制：1000 ms

题目描述

对一个长度为 $N$ 的序列 $\{a_n\}(a_i\in[0,2^{16}-1])$，进行如下两种，共计 $M$ 个操作：

  1. A x$(x\ge0)$：$a_i=a_i+x\mod2^{16}$

  2. Q i：询问 $Card\{k\mid(a_k\;\&\;2^i)>0,1\le k\le N,k\in\mathbb{Z}\}$ 的结果

其中 $\&$ 运算符为相当于 C/C++ 中的&

给定初始序列和操作序列，请你模拟操作过程，并计算所有 $Q$ 操作的相应的结果的和。

输入格式

输入的第一行包含两个以空格分隔的整数，分别代表 $N,M$

接下来的 $N$ 行每行包含一个整数，代表初始序列

接下来的 $M$ 行，每行描述一个操作，格式如题目中所述

输出

输出包含一个整数，表示所有 $Q$ 操作的结果的和

样例

样例输入 1

3 5
1
2
4
Q 1
Q 2
A 1
Q 1
Q 2

样例输出 1

5

提示

【样例说明】

初始序列为 $124$

Q 1：仅 $a_2=2$ 满足 $(a_k\;\&\;2^i)>0$，该 $Q$ 操作的结果为 $1$

Q 2：仅 $a_3=4$ 满足 $(a_k\;\&\;2^i)>0$，该 $Q$ 操作的结果为 $1$

A 1：原序列变为 $235$

Q 1：仅 $a_1=2,a_2=3$ 满足 $(a_k\;\&\;2^i)>0$，该 $Q$ 操作的结果为 $2$

Q 2：仅 $a_3=5$ 满足 $(a_k\;\&\;2^i)>0$，该 $Q$ 操作的结果为 $1$

$1+1+2+1=5$，所以最终结果为 $5$

【数据规模】

$30\%$ 的数据满足 $1\le N\le100,1\le M\le1000$

$100\%$ 的数据满足 $1\le N,M\le10^5$