该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题意：

一份清单最初按顺序写有 $n$ 个整数。清单中的位置从 $1$ 开始编号，每次修改后重新连续编号。

依次处理以下操作：

• I p x：在清单的前 $p$ 个数之后插入整数 $x$。$p=0$ 表示插在最前面，$p$ 等于当前长度时表示插在最后面。
• D p：删除当前第 $p$ 个数。
• Q p：询问当前第 $p$ 个数。如果当前长度小于 $p$，输出 EMPTY。

保证每次插入的位置合法，每次删除的位置存在。相同的整数可以出现多次，每次操作只按照位置确定对象。

输入格式：

第一行两个整数 $n$、$q$（$0 \le n \le 2000$，$1 \le q \le 2000$），分别表示初始长度和操作次数。

若 $n>0$，下一行给出 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$-10^9 \le a_i \le 10^9$）；若 $n=0$，这一行省略。

接下来 $q$ 行，每行给出一条操作。设执行该操作前的清单长度为 $m$：

• I p x：给出整数 $p$、$x$（$0 \le p \le m$，$-10^9 \le x \le 10^9$）。
• D p：给出整数 $p$（$1 \le p \le m$）。
• Q p：给出整数 $p$（$1 \le p \le 4001$）。

输出格式：

对每条 Q 操作输出一行，为询问到的整数或 EMPTY。其他操作不产生输出；没有询问时不输出内容。

样例：

样例输入1：

3 8
10 20 30
Q 2
I 0 5
I 4 40
D 2
Q 2
D 4
I 1 7
Q 4

样例输出1：

20
20
30

样例解释1：

第二次询问时，清单为 $(5,20,30,40)$。最后一次询问时，清单为 $(5,7,20,30)$。

样例输入2：

0 6
Q 1
I 0 9
Q 1
D 1
Q 1
I 0 7

样例输出2：

EMPTY
9
EMPTY