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

题意：

一份清单最初为空，元素位置从 $1$ 开始编号。依次处理以下操作：

• ADD x：在清单末尾增加整数 $x$。
• SET p x：将当前第 $p$ 个数改为 $x$，保证这个位置存在。
• UNDO：撤销最近一条尚未被撤销的修改。修改仅指 ADD 和 SET。没有可撤销修改时，不发生变化。
• REDO：恢复最近一次被撤销、且仍然可以重做的修改。连续多次撤销后，按照撤销顺序的相反顺序恢复。没有可重做修改时，不发生变化。
• GET p：输出当前第 $p$ 个数。这个位置不存在时，输出 EMPTY。

规则还包括：

1. 执行新的 ADD 或 SET 时，之前所有尚未重做的修改都立即失去重做资格。
2. 即使 SET 写入的数与原值相同，也算一次新的修改，能够被撤销，并且会清除原有的重做资格。
3. GET 不修改清单，也不影响撤销、重做的顺序。无事可做的 UNDO、REDO 同样不产生新的修改。
4. 撤销 ADD 会删除它增加的末尾元素；撤销 SET 会恢复该位置修改前的数值。重做后，这条修改再次可以被撤销。

输入格式：

第一行一个整数 $q$（$1 \le q \le 2\times10^5$），表示操作次数。

接下来 $q$ 行，每行给出一条上述操作。参数范围如下：

• ADD x：整数 $x$（$-10^9 \le x \le 10^9$）。
• SET p x：整数 $p$、$x$（$1 \le p \le m$，$-10^9 \le x \le 10^9$），其中 $m$ 为当前清单长度。
• GET p：整数 $p$（$1 \le p \le q$）。

输出格式：

对每条 GET 操作输出一行，为查询结果或 EMPTY。其他操作不产生输出；没有查询时不输出内容。

样例：

样例输入1：

16
ADD 5
ADD 8
SET 1 9
GET 1
UNDO
GET 1
UNDO
GET 2
REDO
GET 2
ADD 6
REDO
GET 1
UNDO
REDO
GET 3

样例输出1：

9
5
EMPTY
8
5
6

样例解释1：

第一次重做恢复了 ADD 8。随后执行新的 ADD 6，使旧的 SET 1 9 失去重做资格，因此紧接着的 REDO 不改变清单。

样例输入2：

8
UNDO
REDO
ADD 4
SET 1 4
UNDO
GET 1
UNDO
GET 1

样例输出2：

4
EMPTY

样例解释2：

SET 1 4 虽然没有改变数值，但仍占一次修改。撤销它之后，必须再撤销一次，才能撤销 ADD 4。