Bitwise Operations on Integers

Given N integers in the range \([0, 65535]\), perform a series of operations. There are two types of operations:

• Modification Operation: C d — Increase every number by \(d\) and then take modulo \(65536\) (i.e. compute \((x+d) \bmod 65536\)). It is guaranteed that \(0 \le d \le 65535\).
• Query Operation: Q i — Count how many integers have the \(i\)th bit set (i.e. for which \(x \& 2^i > 0\)). Here, \(0 \le i \le 15\).

For each query operation, output the corresponding count.

inputFormat

The first line contains two space-separated integers N and M, where N is the number of integers and M is the number of operations.

The second line contains N space-separated integers, each in the range \([0, 65535]\).

Each of the following M lines contains a single operation in one of the following formats:

• C d — a modification operation.
• Q i — a query operation.

outputFormat

For each query operation, output a single line with the count of integers whose ith bit is non-zero.

sample

5 6
1 2 3 4 5
Q 0
C 1
Q 1
C 2
Q 2
Q 3

3
3
4
1