P6887 [CEOI 2006] Queue

如果你是一个普通的足球迷，你可能知道今年在德国举办的世界杯门票几乎是不可能获得的。贪婪的组织者和足球联合会抢走了大部分可用的门票，并将它们分给了赞助商、朋友和家人。结果是，场馆被旅行者占据，而铁杆球迷则坐在家里观看比赛，中间夹杂着劣质啤酒和无糖口香糖的广告。 还有几张决赛的门票剩下，售票处前排起了长队。随着球迷的到来，他们被依次标记为连续的整数。队伍中的第一个人被标记为 1 号，第二个为 2 号，依此类推。 由于球迷们是前一天晚上到达的，他们不得不在售票窗口开放前等待很长时间，自然有些人需要去洗手间。每次有人需要去洗手间时，他/她会离开队伍，完成任务后再回到队伍中，但不一定回到之前的位置。由于只有一个洗手间，所以在前一个人返回之前，没有人会离开队伍（因此，在任何时刻队伍中最多只有一个人缺席）。 在晚上，总共发生了 N 次洗手间访问。每次访问由两个正整数 A 和 B 描述，表示标记为 A 的人离开队伍，然后在标记为 B 的人前面立即回到队伍中。现在所有的访问都已完成，官员们必须回答一系列问题。每个问题的形式要么是 'P X'，询问标记为 X 的人的位置，要么是 'L X'，询问位置 X 的人的标记。 队伍中的第一个人被认为是在位置 1，第二个在位置 2，依此类推。 编写一个程序，给定访问的描述和若干问题，回答所有的问题。

输入的第一行包含一个整数 N（2 ≤ N ≤ 50 000）——洗手间访问的总次数。 接下来的 N 行中的每一行包含两个不同的整数 A 和 B（1 ≤ A, B ≤ 10^9），描述一次洗手间访问。下一行包含一个整数 Q（1 ≤ Q ≤ 50 000）——问题的总数。 接下来的 Q 行中的每一行包含一个单个字符（大写字母 'P' 或大写字母 'L'）和一个整数 X（1 ≤ X ≤ 10^9），描述一个问题。

输出应包含总共 Q 行。 输出的第 i 行应包含一个整数 R——第 i 个问题的答案。 如果相应的问题是形式 'P Xi'，那么 R 应该是标记为 Xi 的人的最终位置。 如果相应的问题是形式 'L Xi'，那么 R 应该是位置 Xi 的人的标记。

对于错误的解决方案，如果所有形式为 'P X' 的问题都正确回答，或者所有形式为 'L X' 的问题都正确回答，将获得部分分数。对于相应的测试用例，你将获得 50% 的分数。 为了获得部分分数，输出应按照规格格式化。因此，即使你选择只回答一种类型的问题，你仍然应该为所有其他类型的问题生成输出。 题面翻译由 ChatGPT-4o 提供。