题目描述：

在电脑游戏《天狼星探险》中，有 $n$ 名玩家，编号从 $1$ 到 $n$。在之前的任务中，第 $i$ 名玩家积累了 $c_i$ 点经验值。如果两个玩家的经验值相同，我们称他们具有相同的等级，否则经验值较高的玩家等级较高。

游戏由多个回合组成。在每个回合结束时，每个玩家的经验值会增加，增加的值等于其他玩家中比他等级高的不同等级的数量。例如，如果玩家的经验值为 $[2, 5, 5, 1, 2, 10]$，那么第一个玩家的经验值会增加 $2$，因为有两个更高的等级——经验值为 $5$ 的玩家和经验值为 $10$ 的玩家。最后一个玩家的经验值不会增加。玩家的经验值同时变化。也就是说，在我们的例子中，回合结束时玩家的经验值将变为 $[4, 6, 6, 4, 4, 10]$。

你需要回答几个问题。每个问题可以是以下三种类型之一：

1. 在游戏进行 $k$ 回合后，玩家会有多少个不同的等级？
2. 在前 $k$ 回合中，所有玩家的经验值总共增加了多少？
3. 在第 $k$ 回合结束时，第 $i$ 名玩家的经验值是多少？

---

输入格式

第一行给出两个整数 $n, q$ $(1 \le n, q \le 3\cdot 10^5)$，分别表示玩家数量和你需要回答的问题数量。

第二行给出 $n$ 个整数 $c_i$ $(0 \le c_i \le 10^{12})$，表示每个玩家在当前游戏开始时的经验值。

接下来的 $q$ 行描述了问题。每行以一个整数 $t$ $(t \in \{1, 2, 3\})$ 开头，表示问题的类型。

• 如果 $t = 1$，接下来是一个整数 $k$ $(0 \le k \le 10^{12})$，表示回合数。
• 如果 $t = 2$，接下来是一个整数 $k$ $(0 \le k \le 10^{12})$，表示回合数。
• 如果 $t = 3$，接下来是两个整数 $k, i$ $(0 \le k \le 10^{12}, 1 \le i \le n)$，分别表示回合数和我们关心的玩家编号。

---

输出格式

对于每个问题，在输出一行一个整数表示答案。

---

样例 1

输入

6 6
5 4 4 2 2 2
1 0
1 1
1 2
2 1
2 2
3 1 5

输出

3
2
1
8
11
4

在第一个样例中，玩家的经验值变化如下：

回合	$c_1$	$c_2$	$c_3$	$c_4$	$c_5$	$c_6$
游戏开始时	5	4		2
1		5		4
2				5

---

样例 2

输入

5 4
0 3 5 4 2
1 0
1 1
2 1
3 1 1

输出

5
2
10
4

在第二个样例中，玩家的经验值变化如下：

回合	$c_1$	$c_2$	$c_3$	$c_4$	$c_5$
游戏开始时	0	3	5	4	2
1	4	5		5

---

数据范围与提示

对于所有数据，令 $n \le N_{max}, q \le Q_{max}, c_i \le C_{max}, k \le K_{max}$。

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

子任务	分值	$N_{max}$ 的限制	$Q_{max}$ 的限制	$C_{max}, K_{max}$ 的限制	$t$ 的限制	子任务依赖
1	18	5000		$10^4$		0
2	16			$10^7$		0, 1
3	14			$10^{12}$		0, 1, 2
4	7	$3 \cdot 10^5$		$10^7$
5	12	5000		$10^{12}$		0, 1-3
6	14	$3 \cdot 10^5$			$t=1$
7	10				$t\in\{1,2\}$	6
8	9					0, 1-7