Student Assistance Query

With the exam approaching, students are intensifying their revision. Each student has two ability coefficients \(A\) and \(B\). A student will ask another student for assistance if and only if the other student's coefficients are both no less than his own, i.e. for student \(i\) to ask student \(j\), it must hold that \(A_j \ge A_i\) and \(B_j \ge B_i\). When there are multiple possible candidates, the student chooses the one with the minimum difference in \(B\) (i.e. \(B_j - B_i\)). If there is still a tie, the candidate with the minimum difference in \(A\) (i.e. \(A_j - A_i\)) is chosen.

You are given \(n\) commands. Each command is one of the following two types:

• D A B: A student enters with ability coefficients \(A\) and \(B\).
• P i: The \(i\)th student (in order of entry) queries who he should ask for help. It is guaranteed that the \(i\)th student has already entered. Output the index of the chosen candidate. If no student qualifies, output \(-1\).

inputFormat

The first line contains an integer \(n\), the number of commands. Each of the next \(n\) lines contains one command, which is either:

• D A B (a student entering with abilities \(A\) and \(B\)), or
• P i (the \(i\)th student querying for assistance).

outputFormat

For each query command \(P i\), output a single line containing the index of the student who should be asked for help, following the criteria described. If no suitable student exists, output \(-1\).

sample

5
D 3 4
D 4 5
P 1
D 3 5
P 1

2
3