有一个长度为 $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$ 的个数。
## Input
第一行两个正整数 $n,q$。
第二行 $n$ 个正整数 $a_1, a_2, \ldots, a_n$。
接下来 $q$ 行，每行描述一个操作，形如以下三种中的一种：
- `A l r x`
- `P l r`
- `J p`
## Output
对于每个 `J` 操作，输出一行，一个整数，表示答案。
[samples]
## Background
“那以后见到她，会不会笑出来啊？”
“哈，一时半会见不到她的。”
小时候说要一起去看尘寰间的人间烟火，有人欣然接受，长大了说遗忘过去，那人也没有反驳。
其实吧，她们彼此明白，小时候在意的不是什么人间烟火，而是一起。
黑夜里，没有早晨的绯红，也褪去了天边的白光，留下的是她心头的散不去的灰暗。没有星光璀璨，没有满天繁星，她不在乎。她在乎的是那个人心中闪烁的星辰大海。
----
察觉所谓规则秘密，不过取悦于创世神明，早已知晓光明同黑暗般腥风血雨
## Note
**【样例解释】**
- 开始时，$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 效率。