사다리타기

고스트 레그(Ghost leg)는 아미다쿠지(Amidakuji)라고도 부르는 일본의 오래된 추첨 방법이다. 참가자 $n$명이 $n$개의 상품 중 하나씩을 받는다. 게임판은 왼쪽에서 오른쪽으로 1번부터 $n$번까지 번호가 붙은 세로선 $n$개로 이루어진다. 처음에 게임판에는 $m$개의 가로대가 있다. 가로대는 서로 다른 높이에 있으며, 위에서 아래로 1번부터 $m$번까지 번호가 붙는다. $j$번 가로대는 $p_j$번 세로선과 $p_j+1$번 세로선을 잇는다. (아래 힌트의 그림을 참고한다.)

$j$번 세로선의 맨 위에는 $j$번 참가자가 있고, 맨 아래에는 $j$번 상품이 있다. 참가자 $j$가 받는 상품은 다음과 같이 정한다. $j$번 세로선의 위쪽 끝에서 출발해 아래로 내려간다. 가로대를 만나면 반드시 그 가로대를 따라 옆 세로선으로 건너간 뒤 계속 내려간다. 경로가 끝나는 세로선 번호가 참가자의 상품 번호다.

게임판과 $q$개의 사건이 주어진다. 사건은 두 가지 중 하나다. A i는 게임판에서 $i$번 가로대를 제거한다는 뜻이다. B j는 참가자 $j$가 현재 어떤 상품을 받는지 묻는다. B 사건 각각에 대한 답을 구한다.

첫 줄에 참가자 수 $n$과 가로대 수 $m$이 주어진다. ($2 \le n \le 1000000$, $1 \le m \le 1000000$) 둘째 줄에는 가로대의 위치 $p_1, p_2, \ldots, p_m$이 주어진다. ($1 \le p_i \le n-1$) 다음 줄에는 사건의 수 $q$가 주어진다. ($1 \le q \le 1000000$) 이어서 $q$개의 줄에 A i 또는 B j 형식의 사건이 한 줄에 하나씩 주어진다. 같은 가로대는 두 번 이상 제거되지 않으며, B 사건은 적어도 하나 있다.

B 사건마다 답을 한 줄에 하나씩 출력한다. 사건이 주어진 순서대로 출력한다.

그림은 초기 게임판을 나타낸다. 1번 참가자는 2번 가로대를 지나고, 이어서 5번 가로대를 지나 3번 상품을 받는다.