给定一个初始长为 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，输出一行一个整数，代表查询值。