P11101 [ROI 2022] 天狼星探险队 (Day 2)

翻译自 [ROI 2022 D2T2](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-roi-2022-day2.pdf)。 “天狼星探险队”游戏中有 $n$ 个玩家，编号从 $1$ 到 $n$。每个玩家在之前的任务中积累了 $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\le300,000$），分别表示玩家数量和需要回答的问题数量。 第二行包含 $n$ 个整数 $c_i$（$0\le c_i\le10^{12}$），表示当前游戏开始时每个玩家的经验值。 接下来有 $q$ 行问题。每行以整数 $t$（$t\in\{1，2，3\}$）开头，表示问题类型。 - 如果 $t=1$，则后面是整数 $k$（$0\le k\le10^{12}$），表示回合数。 - 如果 $t=2$，则后面是整数 $k$（$0\le k\le10^{12}$），表示回合数。 - 如果 $t=3$，则后面是两个整数 $k$ 和 $i$（$0\le k\le10^{12}，1\le i\le n$），表示回合数和玩家编号。 在所有问题中，$k=0$ 表示游戏开始时到进行第一轮之前的时刻。

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

下图是两个样例中游戏进行时玩家的经验值变化。  全部数据范围见输入格式。 | Subtask | 分值 | $n\le$ | $q\le$ | $c,k\le$ | $t$ | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $18$ | $5000$ | $5000$ | $10^4$ | | | $2$ | $16$ | $5000$ | $5000$ | $10^7$ | | | $3$ | $14$ | $5000$ | $5000$ | $10^{12}$ | | | $4$ | $7$ | $3\times10^5$ | $3\times10^5$ | $10^7$ | | | $5$ | $12$ | $5000$ | $3\times10^5$ | $10^{12}$ | | | $6$ | $14$ | $3\times10^5$ | $3\times10^5$ | $10^{12}$ | $t=1$ | | $7$ | $10$ | $3\times10^5$ | $3\times10^5$ | $10^{12}$ | $t\in\{1,2\}$ | | $8$ | $9$ | $3\times10^5$ | $3\times10^5$ | $10^{12}$ | |