你拥有一个长度为 1 的整数序列 $A = (1)$。你需要按顺序处理 $Q$ 个查询。

查询共有三种类型： 设 $n$ 为每个查询前序列 $A$ 的长度，且 $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$。如果 $x \le n$，输出 $a_x$。

输入格式

输入通过标准输入按以下格式给出：

$Q$ $t_1 \ x_1$ $t_2 \ x_2$ $\vdots$ $t_Q \ x_Q$

其中 $t_i$ ($1 \le i \le Q$) 是一个整数，表示查询类型，且 $t_i \in \{1, 2, 3\}$。

• $1 \le Q \le 2 \times 10^5$
• $1 \le x \le 10^9$
• 至少存在一个输出查询。
• 所有输入值均为整数。

输出格式

打印 $q$ 行，其中 $q$ 是满足 $t_i = 3$ 的查询数量。在第 $j$ 行 ($1 \le j \le q$)，输出第 $j$ 个类型为 3 的查询的结果。

样例

样例输入 1

6
1 4
3 3
1 3
3 2
2 3
3 2

样例输出 1

-1
4
3

样例输入 2

8
1 8
2 5
2 5
3 7
3 8
3 9
2 3
3 1

样例输出 2

5
1
-1
3

说明

在第一个样例中，$A$ 的变化如下：

• 查询 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)$