题目描述

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

1. A x：$(x \geq 0)$：$a_i=(a_i+x) \bmod 2^{16}$。
2. Q i：询问 $Card\{k|(a_k\& 2^i)>0,~1 \leq k \leq N,~k \in \mathcal Z\}$ 的结果。

其中 & 运算符为相当于 C/C++ 中的 & 或者 Pascal 中的 and。

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

输入格式

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

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

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

输出格式

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

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

5

样例解释

初始序列为：1 2 4。

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

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

A 1：原序列变为 2 3 5。

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

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

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

数据范围

对于 $30\%$ 的数据满足 $1 \leq N \leq 100,~1 \leq M \leq 1000$；

对于 $100\%$ 的数据满足 $1 \leq N,M \leq 10^5$。