Ispiti

Είναι ώρα εξετάσεων στο χωριό του Mirko. Όλοι θέλουν να περάσουν τις εξετάσεις με όσο το δυνατόν λιγότερη προσπάθεια, που δεν είναι εύκολο. Ο Mirko συνειδητοποίησε ότι θα ήταν καλύτερο για αυτόν να βρει κάποιον που να ξέρει περισσότερα από αυτόν και μάθει από αυτόν. Όλοι έκαναν το ίδιο και τώρα όλοι ψάχνουν από κάποιον να μάθουν.
Μπορούμε να μοντελοποιήσουμε πόσο καλά είναι προετοιμασμένος ένας μαθητής για τις εξετάσεις με δύο ακέραιους αριθμούς, τον ~A~ και τον ~B~. Ο αριθμός ~A~ αντιπροσωπεύει πόσο καλά ένας μαθητής κατανοεί το θέμα, ενώ ο αριθμός ~B~ είναι ανάλογος της ποσότητας των γνώσεών τους.
Ως αρχηγός του χωριού, ο Mirko αποφάσισε ότι ένας μαθητής θα ζητήσει βοήθεια από έναν άλλο μαθητή μόνο αν αυτός ο μαθητής έχει και τους δύο αριθμούς μεγαλύτερους ή ίσους με τους αριθμούς του πρώτου μαθητή (κανένας μαθητής δεν θα ρωτήσει κάποιος που δεν καταλαβαίνει το θέμα τόσο καλά όσο οι ίδιοι ή που ξέρει λιγότερα).
Επιπλέον, οι μαθητές θα προσπαθήσουν να ελαχιστοποιήσουν τη διαφορά στην ποσότητα γνώσης (ώστε να μην ενοχλούν τους μαθητές που είναι πολύ καλύτεροι). Εάν αυτή η επιλογή δεν είναι μοναδική, θα προσπαθήσουν να ελαχιστοποιήσουν τη διαφορά στην κατανόηση.
Το χωριό του Mirko έχει γίνει πρόσφατα ένα πολύ δημοφιλές προάστιο και οι νέοι φοιτητές συνεχίζουν να μετακομίζουν (για την εξέταση). Με τους αυστηρούς κανόνες του Mirko, μπερδεύονται και δεν ξέρουν πού να πάνε.Αποφάσισαν να ζητήσουν βοήθεια από έναν προγραμματιστή από ένα γειτονικό χωριό.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει έναν ακέραιο αριθμό ~N (1 \le N \le 200\,000)~, τον αριθμό των ερωτημάτων και των αφίξεων στο χωριό. Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει είτε:

• «~D\;A\;B~», ένας μαθητής έχει μετακομίσει του οποίου οι γνώσεις είναι ~A~ και ~B~

• "~P\;i~", ο ~i~-οστός μαθητής που θα μετακομίσει θέλει να μάθει από ποιον να ζητήσει βοήθεια

Οι αριθμοί ~A~ και ~B~ είναι μεταξύ ~1~ και ~2\,\cdot\,10^9~. Δεν υπάρχουν δύο μαθητές που να έχουν και τους δύο αριθμούς ίσους.

Έξοδος

Για κάθε ερώτημα (γραμμή που περιέχει "~P~ ~i~"), εκτυπώστε από ποιον μαθητή πρέπει να ζητήσει βοήθεια ο ~i~-οστός μαθητής. Οι μαθητές είναι αριθμημένοι με τη σειρά που μετακόμισαν στο χωριό (ξεκινώντας από το ~1~). Εάν ένας μαθητής δεν μπορεί να βοηθηθεί, εκτυπώστε "NE".

Παραδείγματα

input

6
D 3 1
D 2 2
D 1 3
P 1
P 2
P 3

output

NE
NE
NE

input

6
D 8 8
D 2 4
D 5 6
P 2
D 6 2
P 4

output

3
1

input

7
D 5 2
D 5 3
P 1
D 7 1
D 8 7
P 3
P 2

output

2
4
4