Description

For a sequence $\{a_n\}$ of length $N$ $(a_i \in [0, 2^{16} - 1])$, perform the following two types of operations, for a total of $M$ operations:

1. A x $(x \ge 0)$: $a_i = a_i + x \mod 2^{16}$.

2. Q i: Query the value of $Card\{k \mid (a_k\;\&\;2^i) > 0, 1 \le k \le N, k \in \mathbb{Z}\}$.

Here, the $\&$ operator is the same as & in C/C++ or and in Pascal.

Given the initial sequence and the list of operations, simulate the process and compute the sum of the results of all Q operations.

Input Format

The first line contains two integers $N, M$ separated by spaces, representing $N$ and $M$.

The next $N$ lines each contain one integer, representing the initial sequence.

The next $M$ lines each describe one operation, in the format stated in the description.

Output Format

Output one integer, representing the sum of the results of all Q operations.

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

5

Hint

The initial sequence is $1\;2\;4$.

Q 1: Only $a_2 = 2$ satisfies $(a_k\;\&\;2^i) > 0$, so the result of this Q operation is $1$.

Q 2: Only $a_3 = 4$ satisfies $(a_k\;\&\;2^i) > 0$, so the result of this Q operation is $1$.

A 1: The original sequence becomes $2\;3\;5$.

Q 1: Only $a_1 = 2, a_2 = 3$ satisfy $(a_k\;\&\;2^i) > 0$, so the result of this Q operation is $2$.

Q 2: Only $a_3 = 5$ satisfies $(a_k\;\&\;2^i) > 0$, so the result of this Q operation is $1$.

$1 + 1 + 2 + 1 = 5$, so the final result is $5$.

Constraints:

$30\%$ of the testdata satisfy $1 \le N \le 100, 1 \le M \le 1000$.

$100\%$ of the testdata satisfy $1 \le N, M \le 10^5$.

Translated by ChatGPT 5