题目描述

对一个长度为$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++中的&或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^i)>0$，该$Q$操作的结果为$1$

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

A 1：原序列变为$2\;3\;5$

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$