说明

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

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

提示

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

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