题目背景

翻译自 ROI 2022 D2T2。

“天狼星探险队”游戏中有 $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$ 表示游戏开始时到进行第一轮之前的时刻。

输出格式

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

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

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

5
2
10
4

提示

下图是两个样例中游戏进行时玩家的经验值变化。

全部数据范围见输入格式。