给定一个初始长为 $n$ 的数列 $a$，下标从 $1$ 开始。共有 $m$ 次操作，类型如下：

1. 在下标 $i$ 处插入元素 $x$，原下标 $i$ 及往后的元素往后移动让位。
2. 删除下标 $i$ 的元素，$i$ 往后的元素往前移动补位。
3. 修改下标 $i$ 的元素值，将其改成 $x$。
4. 查询并输出下标 $i$ 的元素。

对于任意时刻，如果此时下标 $i$ 大于数列长度，忽略此次操作。

输入一行两个整数 $n,m(1\le n,m\le10^5)$。

接下来输入一行 $n$ 个整数，代表初始 $a_i(1\le a_i\le10^9)$。

接下来输入 $m$ 行，每行第一个整数为 $c(1\le c\le4)$，代表操作类型：

1. 若 $c=1$ 或 $c=3$，接下来再输入两个整数 $i,x$。
2. 若 $c=2$ 或 $c=4$，接下来再输入一个整数 $i$。

保证 $1\le i\le2\times10^5,1\le x\le10^9$。保证插入和删除操作总和不超过 $100$ 次。

对每个不被忽略的操作 $4$，输出一行一个整数，代表查询值。