Queue

Time limit2sMemory limit32 MB

Summary

Simulate people repeatedly leaving a queue and reinserting before another person, then answer position and label lookup queries efficiently using a balanced structure like a Fenwick tree or order-statistics tree.

Level: Medium7 of 10
Topics: Segment tree, Binary search, Simulation, Sorting
Solved: No attempts yet

Problem

Fans hoping to buy tickets for this year's World Cup final in Germany have formed a long queue in front of the ticket office.

As the fans arrived, they were labeled with successive integers in arrival order: 1, 2, 3, and so on. The person at the front of the queue is labeled 1, the next is labeled 2, and so on. Initially the person labeled $i$ stands at position $i$ .

While waiting through the night, some fans needed to use the restroom. Whenever a person uses the restroom, they step out of the queue and, upon returning, step back in immediately in front of one specific person (not necessarily at their previous spot). There is only one restroom, so no one steps out before the previous person has returned; hence at most one person is missing from the queue at any moment.

During the night there were $N$ restroom visits in total. Each visit is given by two integers $A$ and $B$ , meaning the person labeled $A$ stepped out of the queue and stepped back in immediately in front of the person labeled $B$ .

After all visits are finished, you must answer $Q$ questions. Each question is one of the following:

P X : report the current position of the person labeled $X$ .
L X : report the label of the person currently at position $X$ .

The front of the queue is position 1, the next is position 2, and so on.

Input

The first line contains the number of restroom visits $N$ ( $2 \le N \le 50\,000$ ).

Each of the following $N$ lines contains two different integers $A$ and $B$ ( $1 \le A, B \le 10^9$ , $A \ne B$ ), describing one restroom visit.

The next line contains the number of questions $Q$ ( $1 \le Q \le 50\,000$ ).

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

Output

Print $Q$ lines.

The $i$ -th line must contain a single integer: the answer to the $i$ -th question.

If the question has the form P X, print the current position of the person labeled $X$ . If it has the form L X, print the label of the person currently at position $X$ .

Examples2

Example 1

Input

Expected output

Example 2

Input

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

Expected output