题目描述

训练营里有一台简易的数字收纳机。

它平时像一个栈一样工作：新数字只能放到最上面，取出数字时也只能从最上面取。

不过老师又给这台机器加了两个调试功能：可以查看或修改“从底往上数第 k 个数字”。因此，如果只会使用普通的栈顶操作，就不太方便完成所有指令。

现在给出 q 条操作指令，请你按顺序维护这台机器，并回答所有查询。

操作共有五种：

• push x：把数字 x 放到最上面。
• pop：如果机器中有数字，就取出最上面的一个；如果没有数字，则什么也不做。
• top：询问当前最上面的数字；如果没有数字，输出 EMPTY。
• get k：询问从底往上数第 k 个数字；如果不存在这个位置，输出 EMPTY。
• change k x：把从底往上数第 k 个数字改成 x；如果不存在这个位置，则什么也不做。

这里“从底往上数第 1 个数字”就是最早还留在机器里的那个数字。

输入格式

第一行输入一个整数 q，表示操作数量。

接下来 q 行，每行输入一条操作指令。

输出格式

对于每条 top 或 get 指令，输出一行。

如果对应位置有数字，输出这个数字；否则输出 EMPTY。

样例输入

10
push 4
push 9
get 1
change 1 7
get 1
top
pop
top
pop
top

样例输出

4
7
9
7
EMPTY

样例解释

先后放入 4 和 9 后，从底往上第 1 个数字是 4，最上面的数字是 9。

执行 change 1 7 后，底部的 4 被修改成 7。

最后两次 pop 会依次取出 9 和 7，机器变为空。

数据范围

• $1 <= q <= 2\times10^5$
• $1 <= x <= 10^9$
• $1 <= k <= 2\times10^5$
• 输入保证操作名称只会是 push、pop、top、get、change 之一。