SP28597 BDOI16A - Guess the Queue

**猜队列** 在巴士城，出行唯一的交通工具是公交车。人们需要排队等候才能上车。每个人都有一个独特的公交**ID**。队伍最前面的人就是第一位，而最靠后的人是最后一位。显然，最前面的会第一个上车，最后面的则最后上车。 虽说入队应该从后排进行，但迟到的人有时候会选择另一种方式插队，虽然这样非常不礼貌。由于队伍两侧被围栏阻挡，插队只能从队伍前方进入。此外，耐心耗尽的人可能会选择直接离开队伍，从后方步行去目的地。 你的任务是处理以下三种操作： 1. ‘**1 _x y_’：如果 _x_ 是‘**B**’，ID 为 _y_ 的人从队尾进入；如果 _x_ 是‘**F**’，则从队首进入。 2. ‘**2 _x_’：如果 _x_ 是‘**B**’，队尾的人离开队伍；如果 _x_ 是‘**F**’，则队首的人离开。 3. ‘**3 _x y_’：如果 _x_ 是‘**D**’，查询队伍中第 _y_ 位的人的 **ID** ；如果 _x_ 是‘**P**’，查询 ID 为 _y_ 的人当前所在的位置。

输入的第一行是测试用例的数量 _T_ **(1 ≤** _T_ **≤ 5)**。接下来是 _T_ 个测试用例。 每个测试用例以一个整数 _N_ 开始，表示操作的总数。接下来的 _N_ 行，每行表示一种操作，按顺序给出。 保证输入的操作都是有效的，因此对于第二种操作，队伍总是非空；对于第三种操作，给定的位置或 **ID** 必须已经在队伍中。此外，已经离开队伍的人不会重新加入。

对于每个测试用例，输出一个用例编号，格式为“**Case x:**”，其中 _x_ 是用例编号。 对于每个第三种操作，输出一个整数，表示该查询的结果。

对于简单版本，**1 ≤** _N_ **≤ 2000** 对于困难版本，**1 ≤** _N_ **≤ 200000** 一般情况下， **1 ≤ 每个 ID ≤ 10^9**，每人的 ID 唯一 **1 ≤ 每个位置 ≤ 当前队伍的大小** **样例输入** ``` 1 7 1 B 1 1 B 2 1 F 3 3 D 3 2 B 1 F 4 3 D 2 ``` **样例输出** ``` Case 1: 2 3 ``` **样例解释** 在这个测试用例中，需要执行 7 个操作。 开始时，队伍为空。ID 分别为 1 和 2 的两人从后方入队，接着 ID 为 3 的人从前方入队。现在队伍中有 3 个人，第 3 位的是 ID 为 2 的人。 后来，ID 为 2 的人从队尾离队，只剩下两个人。 最后，ID 为 4 的人从前方入队，现在队伍中又有 3 个人，第 2 位的是 ID 为 3 的人。 **本翻译由 AI 自动生成**