题目描述

石宇浩学长调试智能车时，常常把参数调的越来越烂。为此，他制作了一台固件回滚时光机，用历史栈保存参数状态。

系统初始参数为 x，随后执行 q 条命令：

• SET y：将参数设置为 y，并清空所有可重做记录；
• UNDO：撤销最近一次仍可撤销的 SET，若无法撤销则不做任何操作；
• REDO：重做最近一次被撤销的操作，若无法重做则不做任何操作；
• QUERY：输出当前参数。

输入格式

第一行输入一个整数 x 和一个整数 q。

接下来 q 行，每行输入一条命令。

输出格式

每遇到一次 QUERY，输出一行当前参数。

样例

10 10
QUERY
SET 20
SET 30
UNDO
QUERY
UNDO
REDO
SET 7
REDO
QUERY

10
20
7

数据范围与限制

• -10^18 <= x, y <= 10^18；
• 1 <= q <= 200000；
• 至少有一条 QUERY 命令；
• 时间限制：1 秒；
• 空间限制：64 MiB。