AT_tupc2023_f.Hotel

有一个长度为 $1$ 的整数序列 $A=(1)$。现给出 $Q$ 个查询，请按顺序依次处理这些查询。

查询共有以下 $3$ 种类型。

每次查询处理前，设当前的数列 $A$ 长度为 $n$，为 $A=(a_{1},a_{2},\dots,a_{n})$。

• 1 x ：将 $A$ 替换为长度为 $n+1$ 的数列 $(x,a_{1},a_{2},\dots,a_{n})$。
• 2 x ：将 $A$ 替换为长度为 $2n$ 的数列 $(x,a_{1},x,a_{2},\dots,x,a_{n})$。
• 3 x ：如果 $x>n$，输出 $-1$；否则输出 $a_{x}$。

输入从标准输入读入，格式如下所示：

$Q$ $t_1$ $x_1$ $t_2$ $x_2$ ⋮ $t_Q$ $x_Q$

这里，$t_i$ $(1\leq i\leq Q)$ 表示第 $i$ 个查询的类型，是 $1$、$2$ 或 $3$ 中的一个整数。

设查询中满足 $t_i=3$ 的有 $q$ 次。请输出 $q$ 行，第 $j$ 行输出第 $j$ 次此类查询的答案。

样例解释 1

查询 $1$ 前：$A=(1)$
查询 $1$ 后：$A=(4,1)$
查询 $2$ 后：$A=(4,1)$
查询 $3$ 后：$A=(3,4,1)$
查询 $4$ 后：$A=(3,4,1)$
查询 $5$ 后：$A=(3,3,3,4,3,1)$
查询 $6$ 后：$A=(3,3,3,4,3,1)$
如上所示。

数据范围

• $1 \leq Q \leq 2\times 10^5$
• $1\leq x\leq 10^{9}$
• 至少存在一个输出查询
• 输入均为整数

由 ChatGPT 5 翻译