PIPIOJ

Description

$pipi$ 有一个长度为 $n$ 的数组 $a_1,a_2,...,a_n$ ，他希望你支持 $k$ 次操作，每次操作为下面几个操作之一：
$1$ 反转数组（即对于 $i=1,2,...,\lfloor\frac{n}{2}\rfloor$ ，依次执行操作 $swap(a_i,a_{n-i+1})$
$2$ 输出 $a_i$ ，随后删除 $a_1$ ，其它元素往前移动（即对于 $i=1,2,...,n-1$ ，依次执行操作 $a_i=a_{i+1}$ ），执行操作后数组的长度减 $1$
$3$ 输出 $a_n$ ，随后删除 $a_n$ ，执行操作后数组的长度减 $1$
$4\ val$ 在数组前面插入一个值 $val$ （即对于 $i=n+1,n,...,2$ ，依次执行操作 $a_i=a_{i-1}$ ，最后再执行操作 $a_1=val$ ），执行操作后数组的长度加 $1$
$5\ val$ 在数组后面插入一个值 $val$ （即执行操作 $a_{n+1}=val$ ），执行操作后数组的长度加 $1$

Input

第一行输入两个整数 $n,k(1\le n,k\le 300000)$
第二行 $n$ 个整数 $a_1,a_2,...,a_n(1\le a_i\le 10^9)$
接下来 $k$ 行每行输入两个整数 $op,val(1\le op\le 5$ ，如果 $1\le op\le 3,val=0,$ 否则 $1\le val\le 1000000000)$
当 $1\le op\le 3$ 时， $val$ 不起任何作用，仅为了输入方便。
数据保证执行 $2,3$ 操作时数组非空。

Output

对于每个 $2,3$ 操作，输出对应的结果，占一行。

Sample Input

Sample Output

HINT

第 $1$ 次操作为 $1\ 0$ ，数组被反转为 $5\ 4\ 3\ 2\ 1$
第 $2$ 次操作为 $2\ 0$ ，输出第一个元素 $5$ ，随后数组变为 $4\ 3\ 2\ 1$
第 $3$ 次操作为 $3\ 0$ ，输出最后一个元素 $1$ ，随后数组变为 $4\ 3\ 2$
第 $4$ 次操作为 $4\ 5$ ，在数组前面插入一个 $5$ ，随后数组变为 $5\ 4\ 3\ 2$
第 $5$ 次操作为 $5\ 8$ ，在数组后面插入一个 $8$ ，随后数组变为 $5\ 4\ 3\ 2\ 8$
第 $6$ 次操作为 $1\ 0$ ，数组被反转为 $8\ 2\ 3\ 4\ 5$
第 $7$ 次操作为 $2\ 0$ ，输出第一个元素 $8$ ，随后数组变为 $2\ 3\ 4\ 5$
第 $8$ 次操作为 $3\ 0$ ，输出最后一个元素 $5$ ，随后数组变为 $2\ 3\ 4$

Source/Category

中等 STL