대기열

올해 독일 월드컵 결승전 입장권을 구하려는 팬들이 매표소 앞에 긴 대기열을 이루고 있습니다.

팬들은 도착한 순서대로 1, 2, 3, ... 과 같이 연속한 정수 번호를 부여받았습니다. 대기열의 맨 앞에 선 사람이 1번, 그다음이 2번, ... 입니다. 처음에는 번호가 $i$인 사람이 $i$번째 위치에 서 있습니다.

밤새 기다리는 동안 일부 사람은 화장실에 다녀와야 했습니다. 화장실에 다녀오는 사람은 대기열에서 잠시 빠져나갔다가, 돌아올 때는 이전과 같은 자리가 아니라 특정한 사람 바로 앞에 끼어들어 섭니다. 화장실은 하나뿐이므로 앞사람이 돌아오기 전에는 다음 사람이 빠져나가지 않으며, 따라서 어느 순간에도 대기열에서 빠져 있는 사람은 최대 한 명입니다.

밤 동안 총 $N$번의 화장실 방문이 있었습니다. 각 방문은 두 정수 $A$와 $B$로 주어지며, 번호가 $A$인 사람이 대기열에서 빠져나갔다가 번호가 $B$인 사람 바로 앞으로 다시 들어왔음을 뜻합니다.

모든 방문이 끝난 뒤, 총 $Q$개의 질문에 답해야 합니다. 각 질문은 다음 두 가지 중 하나입니다.

• 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$, $A \ne B$). 이는 한 번의 화장실 방문을 나타냅니다.

그다음 줄에는 질문의 개수 $Q$가 주어집니다 ($1 \le Q \le 50\,000$).

이어지는 $Q$개의 줄에는 각각 대문자 한 글자(P 또는 L)와 정수 $X$가 주어집니다 ($1 \le X \le 10^9$). 이는 한 개의 질문을 나타냅니다.

총 $Q$개의 줄을 출력합니다.

$i$번째 줄에는 $i$번째 질문의 답이 되는 정수 하나를 출력합니다.

질문이 P X 형태라면 번호가 $X$인 사람의 현재 위치를, L X 형태라면 $X$번째 위치에 서 있는 사람의 번호를 출력합니다.