문제

문제 번호와 난이도 쌍으로 구성된 추천 문제 데이터베이스를 관리하라. 다음 세 종류의 명령을 처리한다.

• recommend x : x가 1이면 추천 문제 리스트에서 가장 어려운 문제의 번호를 출력한다. 가장 어려운 문제가 여러 개라면 문제 번호가 큰 것을 출력한다. x가 -1이면 가장 쉬운 문제의 번호를 출력한다. 가장 쉬운 문제가 여러 개라면 문제 번호가 작은 것을 출력한다.
• add P L : 추천 문제 리스트에 난이도가 L인 문제 번호 P를 추가한다. (추천 문제 리스트에 없는 문제 번호 P만 입력으로 주어진다. 이전에 추천 문제 리스트에 있었던 문제 번호가 다른 난이도로 다시 들어올 수 있다.)
• solved P : 추천 문제 리스트에서 문제 번호 P를 제거한다. (추천 문제 리스트에 있는 문제 번호 P만 입력으로 주어진다.)

입력

첫 번째 줄에 초기 데이터베이스에 들어 있는 문제의 개수 \(N\)이 주어진다.

두 번째 줄부터 \(N + 1\) 줄까지 문제 번호 \(P\)와 난이도 \(L\)가 공백으로 구분되어 주어진다.

\(N + 2\)번째 줄에는 입력될 명령문의 개수 \(M\)이 주어진다.

그 다음 줄부터 \(M\)개의 명령문이 입력된다.

출력

recommend 명령이 주어질 때마다 문제 번호를 한 줄씩 출력한다. 최소 한 번의 recommend 명령어가 들어온다.

제한

• \(1 \le N, P \le 100,000\)

• \(1 \le M \le 10,000\)

• \(1 \le L \le 100\), \(L\)은 자연수

• \(x = \pm 1\)

예제 입력 1

5
1000 1
1001 2
19998 78
2667 37
2042 55
8
add 1402 59
recommend 1
solved 1000
solved 19998
recommend 1
recommend -1
solved 1001
recommend -1

예제 출력 1

19998
1402
1001
2667