如果你是一个普通的足球迷，你可能知道要获得今年德国世界杯的门票几乎是一件不可能完成的任务。贪婪的组织者和足球联合会抢占了大部分可用门票，并将其分发给赞助商、朋友和家人。结果，名流们涌入了赛场，而铁杆球迷只能坐在家里，在插播着劣质啤酒和无糖口香糖广告的间隙中观看比赛。

决赛还剩几张门票，售票处前排起了长队。当球迷们到达时，他们被标记为连续的整数。队伍中的第一个人被标记为 1，第二个人被标记为 2，依此类推。

由于球迷们在前一天晚上就到达了，他们在售票窗口开放前必须等待很长时间，自然地，其中一些人需要上厕所。每次有人需要上厕所时，他/她就会走出队列，在完成事情后重新回到队列中，但回到队列中的位置不一定与之前相同。由于只有一个厕所可用，在前一个人返回之前，没有人会离开队列（因此，在任何时刻，队列中最多只有一个人缺席）。

在这一整晚中，总共发生了 $N$ 次上厕所的行为。每次上厕所由两个正整数 $A$ 和 $B$ 描述，表示标记为 $A$ 的人走出队列，然后重新进入队列并紧挨着排在标记为 $B$ 的人前面。现在所有上厕所的行为都已结束，工作人员需要回答一系列问题。每个问题要么是 'P X' 的形式，询问标记为 $X$ 的人的位置；要么是 'L X' 的形式，询问在位置 $X$ 的人的标记。

队列中的第一个人被认为在位置 1，第二个人在位置 2，依此类推。

编写一个程序，在给定上厕所行为的描述和若干问题的情况下，回答所有问题。

输入格式

输入的第一行包含一个整数 $N$ ($2 \le N \le 50\,000$) —— 上厕所的总次数。

接下来的 $N$ 行，每行包含两个不同的整数 $A$ 和 $B$ ($1 \le A, B \le 10^9$)，描述一次上厕所的行为。

下一行包含一个整数 $Q$ ($1 \le Q \le 50\,000$) —— 问题总数。

接下来的 $Q$ 行，每行包含一个字符（大写字母 'P' 或大写字母 'L'）和一个整数 $X$ ($1 \le X \le 10^9$)，描述一个问题。

输出格式

输出应包含共 $Q$ 行。

输出的第 $i$ 行应包含一个整数 $R$ —— 第 $i$ 个问题的答案。

如果对应的问题是 'P X' 的形式，则 $R$ 应为标记为 $X$ 的人的最终位置。

如果对应的问题是 'L X' 的形式，则 $R$ 应为在位置 $X$ 的人的标记。

子任务

对于未能完全正确但能正确回答某一类所有问题的解法，将给予部分分。如果正确回答了所有 'P X' 形式的问题，或者正确回答了所有 'L X' 形式的问题，你将获得该测试点 50% 的分数。

为了获得部分分，输出格式必须符合规范。因此，即使你选择只回答一种类型的问题，你仍然需要为另一种类型的所有问题输出占位内容。

样例

输入 1

2
6 3
9 6
8
L 1
L 2
L 3
L 4
P 1
P 2
P 3
P 4

输出 1

1
2
9
6
1
2
5
6

输入 2

5
7 2
2 7
9 7
10 1
100005 99995
9
L 1
P 2
L 2
P 7
L 7
P 9
P 10
P 99999
L 100000

输出 2

10
3
1
5
4
4
1
100000
99999