Sequence Operations with Popcount Queries

You are given a sequence of length \(n\) where the \(i\)-th element is \(a_i\). You need to perform \(q\) operations on the sequence. The operations are of three types:

• A l r x: For every index \(i\) with \(l \le i \le r\), update \(a_i \gets a_i + x\).
• P l r: For every index \(i\) with \(l \le i \le r\), update \(a_i \gets \operatorname{popcount}(a_i)\), where \(\operatorname{popcount}(x)\) denotes the number of \(1\)'s in the binary representation of \(x\).
• J p: Query the value of \(a_p\). Output the answer for this query.

Note: All indices are 1-indexed.

inputFormat

The first line contains two integers \(n\) and \(q\) denoting the length of the sequence and the number of operations respectively.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the initial sequence.

Each of the next \(q\) lines contains an operation in one of the following formats:

• A l r x
• P l r
• J p

outputFormat

For each query of type J, output the current value of \(a_p\) on a new line.

sample

3 3
1 2 3
J 2
A 1 3 1
J 2

2
3