Simulated Sequence Operations and Bit Queries

You are given a sequence \(\{a_n\}\) of length \(N\) where each \(a_i \in [0, 2^{16}-1]\). You need to process a total of \(M\) operations on this sequence. There are two types of operations:

1. A x (with \(x \ge 0\)): For every index \(i\), update \(a_i = (a_i + x) \bmod 2^{16}\).
2. Q i: Query the value \(\text{Card}\{ k \mid (a_k \;\&\; 2^i) > 0,\,1 \le k \le N \}\). In other words, count how many elements in the current sequence have the \(i\)-th bit (when represented in binary) set (i.e. equal to 1).

Your task is to simulate the operations in the given order and output the sum of the results for all the query operations (Q operations).

Note: The bitwise AND operator is the same as in C/C++ (denoted by &).

inputFormat

The first line contains two integers (N) and (M). The second line contains (N) integers representing the initial sequence (a_1, a_2, \ldots, a_N), where each (a_i \in [0, 2^{16}-1]). The following (M) lines each represent an operation in one of the following formats:

1. A x where (x \ge 0).
2. Q i where (i) is a non-negative integer representing the bit position (0-indexed).

It is guaranteed that the operations are valid.

outputFormat

Output a single integer which is the sum of the results of all the query (Q) operations.

sample

3 4
1 2 3
A 2
Q 1
A 1
Q 0

2