Background

“Will I laugh if I see her again after that?”

“Haha, I won’t be seeing her for a while.”

When they were young, they said they would go together to see the worldly lights and bustle; someone happily agreed. When they grew up, they said to forget the past, and that person did not argue.

In fact, they both understood that what they cared about when they were young was not those worldly lights, but being together.

In the dark night, there is no morning blush, and the pale light at the horizon has also faded away. What remains is the lingering gloom in her heart. No brilliant starlight, no sky full of stars—she does not care. What she cares about is the sea of stars shining in that person’s heart.

Realizing the so-called secrets of rules is only to please the creator god, she had long known that light and darkness are both filled with bloodshed and foul winds.

Problem Description

There is a sequence of length $n$. Initially, the $i$-th element is $a_i$. You need to perform $q$ operations:

• A l r x: For all $l\le i\le r$, set $a_i\gets a_i+x$.
• P l r: For all $l\le i\le r$, set $a_i\gets\operatorname{popcount}(a_i)$.
• J p: Query the value of $a_p$.

Note: $\operatorname{popcount}(x)$ is the number of $1$ bits in the binary representation of $x$.

Input Format

The first line contains two positive integers $n,q$.

The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n$.

The next $q$ lines each describe one operation, in one of the following three forms:

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

Output Format

For each J operation, output one line with one integer, which is the answer.

5 5
1 2 3 4 5
J 2
A 2 4 3
J 4
P 1 4
J 3

2
7
2

Hint

【Sample Explanation】

• Initially, $a = [1, 2, 3, 4, 5]$.
• For the query J 2, the answer should be $a_2 = 2$.
• After the operation A 2 4 3, $a = [1, 5, 6, 7, 5]$.
• For the query J 4, the answer should be $a_4 = 7$.
• After the operation P 1 4, $a = [1, 2, 2, 3, 5]$.
• For the query J 3, the answer should be $a_3 = 2$.

【Constraints】

This problem uses bundled testdata.

For all data, it is guaranteed that $1\leq n\leq 3\times 10^5$, $1 \le q \le 10^6$, $1 \le l \le r \le n$, $1 \le p \le n$, $1\le a_i, x\le 10^9$.

Random generation method for Subtask 4:

• Take $n=3\times 10^5$ and $q=10^6$.
• Each $a_i$ is chosen uniformly at random from $[1,10^9]$.
• For each operation:
  • Choose one uniformly at random from the 3 types of operations.
  • If it is an A operation, choose 2 integers uniformly at random from $[1,n]$, take the smaller as the left endpoint and the larger as the right endpoint, then choose one integer from $[1,10^9]$ as the parameter x.
  • If it is a P operation, choose 2 integers uniformly at random from $[1,n]$, take the smaller as the left endpoint and the larger as the right endpoint.
  • If it is a J operation, choose one integer uniformly at random from $[1,n]$ as the parameter p.

【Hint】

The maximum I/O volume of this problem reaches 30 MiB, so please pay attention to I/O efficiency.

Translated by ChatGPT 5