Description

Given $N$ integers in $[0, 65535]$, write a program that supports the following operations:

Modification operation: C d, add $d$ to every number. If the result exceeds $65535$, take the result modulo $65536$. ($0 \le d \le 65535$)

Query operation: Q i, count how many integers have a nonzero $i$-th bit. In other words, count how many integers have a positive result when applying the bitwise AND with $2^i$. ($0 \le i \le 15$)

Output the counts for all query operations.

Input Format

The first line contains two positive integers $N$ and $M$, which are the number of integers and the number of operations.

The second line contains $N$ integers in $[0, 65535]$.

The next $M$ lines each contain one operation, in the format described above.

Output Format

Output the count for every Q operation.

3 5
1 2 4
Q 1
Q 2
C 1
Q 1
Q 2

1
1
2
1

Hint

Constraints

Translated by ChatGPT 5