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 翻译