You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

辰辰得到了一个数组，他需要让它有一些古老的功能。

Description

给定一个初始长度为 $n$ 的数组，你要对其进行三个古老的操作：

1. 插入一个数字 $k$ 到第 $x$ 个数字的位置。

例：

1 2 4 5 6

插入 $3$ 到第 $3$ 个数字的位置：

1 2 3 4 5 6

2. 删除第 $i$ 个数字。

例：

1 2 3 4 5

删除第 $3$ 个数字：

1 2 4 5

3. 查询第 $i$ 个数字：

例：

1 8 5 3 9

第 $2$ 个数字为 8。

Format

Input

第一行两个正整数 $n,m$，表示原数组元素个数和操作次数。

第二行 $n$ 个正整数表示原数组元素。

第三行至第 $m+2$ 行，每行第一个数字为 $op$，

若 $op=1$，再输入两个正整数 $x,k$，表示插入元素 $k$ 至第 $x$ 个元素的位置。

若 $op=2$，则输入一个正整数 $x$，表示将第 $x$ 个元素删除。

若 $op=3$，则输入一个正整数 $x$，表示查询第 $x$ 个数字。

Output

对于每个 $op=3$ 的询问，输出一行一个正整数表示答案。

Samples

2 3
1 3
1 2 2
2 1
3 1

2

Limitation

$1\le n,m\le 10^5,1\le a_i\le 10^9$

如果你认为你的代码复杂度正确但是超时，可以在头文件下加上这个：

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")

当然，仅限于此题（但本题一定要加，因为本题卡常），其他题目不知道编译环境千万别加，否则会 CE 两行泪。

注意：请不要用 vector 卡常企图通过此题，本题特意卡了（看看时限就知道了）。