题目描述

译自 ROI 2022 Day2 T2. Экспедиция на Сириус

在电脑游戏《天狼星探险》中，有 $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)$，分别表示回合数和我们关心的玩家编号。

输出格式

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

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$	$4$	$2$	$2$	$2$
$1$	$5$	$5$	$5$	$4$	$4$	$4$
$2$	$5$	$5$	$5$	$5$	$5$	$5$

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$	$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$	$5000$	$10^4$		$0$
$2$	$16$			$10^7$		$0, 1$
$3$	$14$			$10^{12}$		$0, 1, 2$
$4$	$7$	$3 \cdot 10^5$	$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$