Ispiti P88048

Llega el momento de los exámenes en el pueblo de Mirko. Todos quieren aprobar con el mínimo esfuerzo posible, por lo que cada persona intenta encontrar alguien que sepa más que ella para que le ayude a prepararse.

Los conocimientos de cada persona del pueblo se modelan por dos números, $A$ y $B$. El número $A$ indica el conocimiento de la asignatura que están preparando, mientras que el número $B$ indica el conocimiento global de todas las materias.

Como jefe del pueblo, Mirko ha dedicido imponer la siguiente restricción: una persona sólo puede ayudar a otra si la primera tiene ambos números iguales o mayores que la segunda. En caso de haber varias personas con tal característica, hay que escoger a aquella que tenga la menor diferencia en conocimiento global (el número $B$), y en caso de seguir existiendo empate, la que tenga menor diferencia en conocimiento específico (el número $A$).

Por si fuera poco, el pueblo de Mirko es muy popular, y muchos estudiantes vienen adrede a prepararse los exámenes. Con las estrictas reglas del pueblo, y con los continuos cambios de estudiantes, nadie sabe a quién tiene que pedir ayuda. Escribe un programa que lo descubra.

Entrada

La primera línea de la entrada contiene un entero $N$ entre $1$ y $200000$, con el número de preguntas y de llegadas de estudiantes al pueblo. A continuación, cada una de las $N$ líneas siguientes contiene:

• “D A B”, un estudiante con conocimientos $A$ y $B$ acaba de llegar.

• “P i”, el $i$-ésimo estudiante en desplazarse quiere saber a quién tiene que pedir ayuda.

Los números $A$ y $B$ estarán entre $1$ y $2\cdot 10^9$. No habrán dos estudiantes con ambos números iguales.

Salida

Para cada pregunta, escribe el número del estudiante al que debe pedir ayuda. Los estudiantes se numeran en el orden en el que llegan al pueblo (empezando por el 1). Si no es posible ayudarle, escribe “NE”.

Pista

No es prudente intentar resolver este problema sin haber resuelto el problema “Intervalos (2)”.