该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在历经了大大小小数场探险和战斗后，士兵们都得到的不同的荣耀值，今天，将军将为所有的士兵分配他们的军功荣耀。将军会为$n$名士兵分发荣耀值，接下来他将发布$m$条命令。每条命令都有不同的类型和效果。

• 命令类型$1$，会提供其他两个整数$y,z$。表示将$a_y$士兵的荣耀值更改为$z$。
• 命令类型$2$，会提供其他一个整数$y$。表示将所有士兵的荣耀值全部增加$y$。
• 命令类型$3$，会提供其他一个整数$y$。请回答将军，$a_y$士兵的荣耀值是是多少。

输入数据

第一行输入两个整数$n$、$m$。分别代表士兵的人数、将军发布的$m$条命令。

第二行输入$n$个整数$a_i$，每一个整数代表一个士兵初始的荣耀值。

接下来的$m$行，每行输入一个命令类型$x$，和该类型命令所需要提供的整数

(注意: 不同类型提供的整数个数不同)。

输出数据

对于每一次命令类型$3$，都输出一个答案，表示指定士兵的荣耀值是多少,换行隔开。

测试样例

10 11
1 2 3 4 5 6 7 8 9 10
3 2
3 9
2 10
3 1
3 10
1 1 10
2 10
2 10
3 1
3 10
3 9

2
9
11
20
30
40
39

样例解释:

在第一个测试样例中，我们对不同的命令进行解释。

• $3,2$的命令中，我们要回答将军$a_2$的士兵荣耀值，此时还是初始值，所以输出的是$2$。
• $3,9$的命令中，我们要回答将军$a_9$的士兵荣耀值，此时还是初始值，所以输出的是$9$。
• $2,10$ 所有士兵的荣耀值增加$10$。即$a:{11,12,13,14,15,16,17,18,19,20}$
• $3,1$的命令中，我们要回答将军$a_1$的士兵荣耀值，此时输出的是$11$。
• $3,10$的命令中，我们要回答将军$a_{10}$的士兵荣耀值，此时输出的是$20$。
• $1,1,10$，将$a_1$士兵的荣耀值更改为$10$。
• $2,10$ 所有士兵的荣耀值增加$10$。
• $2,10$ 所有士兵的荣耀值增加$10$。
• $3,1$的命令中，我们要回答将军$a_1$的士兵荣耀值，此时输出的是$30$。
• $3,10$的命令中，我们要回答将军$a_{10}$的士兵荣耀值，此时输出的是$40$。
• $3,9$的命令中，我们要回答将军$a_9$的士兵荣耀值，此时输出的是$39$。

数据约定:

所有的数据样例保证:

• $1\leq n,m \leq 10^5$
• $1\leq a_i \leq 10^9$