题目描述

某学校组织活动时，所有同学按顺序排成一列队伍。

为了方便管理，老师需要维护这支队伍。最开始队伍中只有一个同学，编号为 1。

现有若干次操作，请你编写程序维护队伍，并回答查询。

保证所有出现的编号均为正整数，且每个编号在队伍中最多出现一次。

支持以下五种操作：

1. INS_BACK x y：将编号为 $y$ 的同学插入到编号为 $x$ 的同学后面。

2. INS_FRONT x y：将编号为 $y$ 的同学插入到编号为 $x$ 的同学前面。

3. ASK_BACK x：查询编号为 $x$ 的同学后面的同学编号。若不存在，则输出 0。

4. ASK_FRONT x： 查询编号为 $x$ 的同学前面的同学编号。若不存在，则输出 0。

5. DEL x：将编号为 $x$ 的同学从队伍中删除。保证不会删除队伍中最后一个元素。

输入格式

第一行一个整数 $Q$，表示操作次数。

接下来 $Q$ 行，每行表示一种操作，格式如下：

INS_BACK x y
INS_FRONT x y
ASK_BACK x
ASK_FRONT x
DEL x

输出格式

对于每个查询操作，输出一行答案。

10
INS_BACK 1 2
INS_BACK 2 3
ASK_BACK 2
ASK_FRONT 2
INS_FRONT 2 4
ASK_FRONT 2
DEL 2
ASK_BACK 4
ASK_FRONT 3
ASK_FRONT 1

3
1
4
3
4
0

数据范围

• $1 ≤ Q ≤ 2000$
• 所有编号均为正整数且不超过 $10^9$
• 保证：
  • 插入时 $x$ 一定存在，$y$ 一定不存在；
  • 查询时 $x$ 一定存在；
  • 删除时 $x$ 一定存在；
  • 任意时刻队伍非空。