Ticket Queue Reordering

In a long queue for the World Cup final tickets, fans are initially standing in the order of ascending labels (starting from 1). During the long waiting night, a total of \(N\) restroom visits occur. Each visit is specified by two positive integers \(A\) and \(B\), meaning that the person with label \(A\) steps out of the queue and then re-enters immediately in front of the person with label \(B\). At any moment, at most one person is absent from the queue.

After all restroom visits, you are given \(Q\) queries. Each query is of one of the following two forms:

• P X: ask for the 1-indexed position of the person with label \(X\).
• L X: ask for the label of the person at position \(X\).

The initial queue is considered to contain all integers from 1 up to the maximum label that appears in the input, arranged in ascending order. Your task is to simulate all restroom visits sequentially and answer all the queries accordingly.

inputFormat

The first line contains two integers \(N\) and \(Q\): the number of restroom visits and the number of queries.

The following \(N\) lines each contain two integers \(A\) and \(B\) (\(1 \le A, B \le M\)) representing a restroom visit, where the person with label \(A\) leaves the queue and re-enters immediately before the person with label \(B\).

The following \(Q\) lines each contain a query in one of the following forms:

• P X — asking for the current position (1-indexed) of the person with label \(X\).
• L X — asking for the label of the person at position \(X\).

Note: \(M\) is the maximum label encountered in any restroom visit or query.

outputFormat

For each query, output a single line with the answer:

• If the query is P X, output the current 1-indexed position of the person with label \(X\).
• If the query is L X, output the label of the person at position \(X</code>).

sample

3 3
2 5
4 1
3 2
P 3
L 1
P 5

3
4
5