为了整理学校下发的数学学习辅助教具——《数字卡片》，你需要将卡片按顺序叠成一堆。

接下来你需要完成 Q 个操作，其中第 $i$ 个操作需要按照规定执行：

• 如果 $t_i = 1$，你需要将一张写着 $x_i$ 的卡片放到卡片堆的最上面。
• 如果 $t_i = 2$，你需要将一张写着 $x_i$ 的卡片放到卡片堆的最下面。
• 如果 $t_i = 3$，你需要输出从上到下第 $x_i$ 张卡片上的数字。

请你编写一个程序，完成这些操作。

通过标准输入给出符合以下格式的输入：

$Q$

$t_1\ \ x_1$

$t_2\ \ x_2$

......

$t_Q\ \ x_Q$

每一次 $t_i = 3$，你都需要输出一个整数，以换行分隔。

数据规模与约定

$2≤Q≤10^5$

$1≤t_i≤3$

当 $t_i = 1,2$ 时，$1≤x_i≤10^9$

当 $t_i = 3$ 时，$1≤x_i≤k$，其中 $k$ 表示目前卡片堆中卡片的数目。

所有 $t_i$ 保证至少有一个 1 或者 2，并且至少有一个 3。

样例解释

1、第一次操作后，卡片堆中的卡片为 $(2)$；第二次操作后，卡片堆中的卡片为 $(1,2)$；第三次操作后，卡片堆中的卡片为 $(1,2,3)$。此时进行三次 $t_i=3$ 的询问，分别询问第一、二、三张，因此输出为 1 2 3，以换行分割。