幻梦 | Dream with Dynamic

“那以后见到她，会不会笑出来啊？” “哈，一时半会见不到她的。” 小时候说要一起去看尘寰间的人间烟火，有人欣然接受，长大了说遗忘过去，那人也没有反驳。 其实吧，她们彼此明白，小时候在意的不是什么人间烟火，而是一起。 黑夜里，没有早晨的绯红，也褪去了天边的白光，留下的是她心头的散不去的灰暗。没有星光璀璨，没有满天繁星，她不在乎。她在乎的是那个人心中闪烁的星辰大海。 ---- 察觉所谓规则秘密，不过取悦于创世神明，早已知晓光明同黑暗般腥风血雨

有一个长度为 $n$ 的序列，开始时第 $i$ 位为 $a_i$。你需要完成 $q$ 次操作： - `A l r x`，对于所有的 $l\le i\le r$，令 $a_i\gets a_i+x$。 - `P l r`，对于所有的 $l\le i\le r$，令 $a_i\gets\operatorname{popcount}(a_i)$。 - `J p`，查询 $a_p$ 的值。 注：$\operatorname{popcount}(x)$ 为 $x$ 的二进制表示中 $1$ 的个数。

第一行两个正整数 $n,q$。 第二行 $n$ 个正整数 $a_1, a_2, \ldots, a_n$。 接下来 $q$ 行，每行描述一个操作，形如以下三种中的一种： - `A l r x` - `P l r` - `J p`

对于每个 `J` 操作，输出一行，一个整数，表示答案。

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

2
7
2

**【样例解释】** - 开始时，$a = [1, 2, 3, 4, 5]$。 - 对询问 `J 2`，应回答 $a_2 = 2$。 - 操作 `A 2 4 3` 后，$a = [1, 5, 6, 7, 5]$。 - 对询问 `J 4`，应回答 $a_4 = 7$。 - 操作 `P 1 4` 后，$a = [1, 2, 2, 3, 5]$。 - 对询问 `J 3`，应回答 $a_3 = 2$。 --- **【数据范围】** **本题采用捆绑测试。** | 子任务编号 | 特殊限制 | 分值 | | :----------: | :----------: | :----------: | | 1 |$n,q\le 2000$| 3 | | 2 |没有 `P` 操作| 7 | | 3 |没有 `A` 操作| 15 | | 4 |数据随机生成| 15 | | 5 |无特殊限制| 60 | 对于全部数据，保证 $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$。 子任务 4 的随机方式： - 取 $n=3\times 10^5$，$q=10^6$； - $a_i$ 从 $[1,10^9]$ 均匀随机选取； - 对于每一个操作： - 从 3 种操作中均匀随机选取一个； - 如果是 `A` 操作，均匀随机从 $[1,n]$ 中选取 2 个整数，将较小的作为区间左端点，较大的作为区间右端点，再从 $[1,10^9]$ 中选取一个整数作为参数 `x`； - 如果是 `P` 操作，均匀随机从 $[1,n]$ 中选取 2 个整数，将较小的作为区间左端点，较大的作为区间右端点； - 如果是 `J` 操作，均匀随机从 $[1,n]$ 中选取一个整数作为参数 `p`。 --- **【提示】** 本题最大 I/O 量达到 30 MiB，请注意 I/O 效率。