暂无测试数据。

蒜头君在序列加工厂上班，刚开始他有一个长度为 $n$ 的序列，编号从 $1$ 开始，第 $i$ 个数为 $a_i$。现在进行 $m$ 次操作，操作存在三种类型：

操作一：查询第 $k$ 个数的大小。

操作二：把第 $k$ 个数的大小改成 $x$。

操作三：将整个序列翻转，即把第 $i$ 个数放到第 $n-i+1$ 个位置。

输入格式

输入数据第一行两个数 $n,m\ (1\le n,m \le 10^5)$，表示数列长度和操作数。

第二行 $n$ 个数，表示 $n$ 个元素初始值 $a_i\ (1\le a_i \le 10^5)$。

以下 $m$ 行，每行开头一个数 $op\ (1\le op \le 3)$，表示操作种类。

若 $op=1$，则后面接一个数 $k\ (1\le k \le n)$,表示查询第 $k$ 个数大小。

若 $op=2$，则后面接两个数$k,x\ (1\le k \le n,1\le x \le 10^5)$，表示第 $k$ 个数改成 $x$。

若 $op=3$，表示序列翻转。

输出格式

对于每个操作一，输出询问对应的答案。

5 7
1 2 3 4 5
1 2
3
1 2
2 2 10
1 2
3
1 4

2
4
10
10