Black Friday is coming. To get the best deal, people come to the mall on Thursday night and wait there until Friday morning. As the security officer, you are organizing people waiting in a line. There are ~10^9~ people in the line. They are labeled with successive integers. The first person in line is labeled with number one, the second with number two, etc.

Since it's still long time before the mall is open, some people have to use the washroom. Each time a person needs to go to washroom, s/he steps out of the line and, after that, steps back into the line, though not necessarilly at the same position as before. Since there is only one washroom available, no person leaves the line before the previous person has returned. At any moment, there is at most one person missing from the line. During the whole night, ~N~ washroom visits have occurred. Each visit is described by two integers ~a~ and ~b~, denoting that the person labeled with ~a~ stepped out of the line and then stepped back into the line immediately in front of the person ~b~.

After all the visits, you want to figure out the position of each person. You need to answer ~Q~ questions. Each question is one of the following types.

• P X: asking for the position of the person labeled with ~X~.

• L X: asking for the label of the person at position ~X~.

Can you write a program to answer all of the ~Q~ questions?

Input Specification

The first line contains one integer ~N~ (~1 \le N \le 5 \times 10^4~), the number of washroom visits.

Each of the following ~N~ lines contains two integers ~a~ and ~b~ (~1 \le a, b \le 10^9~), describing one washroom visit where the person ~a~ stepped out of the line and stepped back into the line in front of the person ~b~.

The second line contains one integer ~Q~ (~1 \le Q \le 5 \times 10^4~), the number of queries.

Each of the following ~Q~ lines contains one character (either P or L) and an integer ~X~ (~1 \le X \le 10^9~), describing a query.

Output Specification

For each query, your program should print one integer.

Constraints

Points	Additional constraints
~20~	~N \le 1\,000~.
~20~	~N \le 15\,000~.
~60~	No additional constraints

Sample Input

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

Sample Output

1
2
9
6
1
2
5
6