题目背景

“那以后见到她，会不会笑出来啊？”

“哈，一时半会见不到她的。”

小时候说要一起去看尘寰间的人间烟火，有人欣然接受，长大了说遗忘过去，那人也没有反驳。

其实吧，她们彼此明白，小时候在意的不是什么人间烟火，而是一起。

黑夜里，没有早晨的绯红，也褪去了天边的白光，留下的是她心头的散不去的灰暗。没有星光璀璨，没有满天繁星，她不在乎。她在乎的是那个人心中闪烁的星辰大海。

察觉所谓规则秘密，不过取悦于创世神明，早已知晓光明同黑暗般腥风血雨

题目描述

有一个长度为 $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\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 效率。