Problem Recommendation System Version 1

Time limit1sMemory limit512 MB

Summary

Maintain a set of problems with difficulty values under add, remove, and query commands that ask for the hardest or easiest problem with a tie-break on problem number.

Level: Medium5 of 10
Topics: Heap, Hash map, Implementation, Sorting
Solved: No attempts yet

Problem

tony9402 recently picked problems for coding test practice on GitHub and organized them by "problem number, difficulty".

He wants to add a new feature for people who study using GitHub.

There are three commands he wants to build. The table below describes each command.


recommend $x$	If $x$ is 1, print the number of the hardest problem in the recommended problem list. If there are several hardest problems, print the one with the largest problem number. If $x$ is -1, print the number of the easiest problem in the recommended problem list. If there are several easiest problems, print the one with the smallest problem number.
add $P$ $L$	Add problem number $P$ with difficulty $L$ to the recommended problem list. (Only a problem number $P$ that is not in the recommended problem list is given as input. A problem number that was in the recommended problem list before can come back with a different difficulty.)
solved $P$	Remove problem number $P$ from the recommended problem list. (Only a problem number $P$ that is in the recommended problem list is given as input.)

The command recommend is given only when the recommended problem list has at least one problem.

The command solved is given only when the recommended problem list has at least one problem number.

Build a recommendation system that performs the commands above.

Input

The first line gives the number of problems $N$ in the recommended problem list.

From the second line to line $N + 1$ , problem number $P$ and difficulty $L$ are given, separated by a space.

Line $N + 2$ gives the number of commands $M$ to be entered.

From the next line, $M$ commands described above are entered.

Output

Every time a recommend command is given, print the problem number, one per line. At least one recommend command is given.

Constraints

$1 \le N, P \le 100,000$
$1 \le M \le 10,000$
$1 \le L \le 100$ , $L$ is a positive integer
$x = \pm 1$

Examples1

Example 1

Input

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

Expected output