Wowow

Στο World of World of Warcraft, υπάρχει ένα πολύ ανταγωνιστικό "σύστημα σκάλας". Μερικές φορές οι παίκτες θα αλλάξουν τη βαθμολογία τους. Επίσης, νέοι παίκτες (συμπεριλαμβανομένων ολοένα και περισσότερων φίλων σας!) συμμετέχουν συνεχώς στο παιχνίδι.

Εσείς και η ομάδα φίλων σας θα θέλατε να διατηρείτε μια απλή βάση δεδομένων με τις βαθμολογίες σας και εσείς, ως ο επιστήμονας υπολογιστών της ομάδας, έχετε επιφορτιστεί με την ευθύνη της συντήρησης της. Μην απογοητεύετε τους φίλους σας!

Είσοδος

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

• ~N~ ~X~ ~R~, όπου ~N~ είναι ο χαρακτήρας 'N' για να δείξει ότι έχει προστεθεί ένας νέος φίλος, ~X~ είναι ένας αριθμός (~1 \le X \le 1\,000\,000~) που προσδιορίζει αυτό το νέο φίλο και ~R~ (~1 \le R \le 10^8~) είναι η βαθμολογία αυτού του νέου φίλου.

• ~M~ ~X~ ~R~, όπου ~M~ είναι ο χαρακτήρας 'M' για να δείξει μία αλλαγή σε έναν υπάρχων φίλο, ~X~ είναι ένας αριθμός (~1 \le X \le 1\,000\,000~) που προσδιορίζει έναν από τους φίλους σας και ~R~ είναι η νέα αλλαγή που δώθηκε σε αυτό τον υπάρχων φίλο σας.

• ~Q~ ~K~, όπου ~Q~ είναι ο χαρακτήρας 'Q' για να δείξει μια ερώτηση, ~K~ είναι ένας αριθμός (~1 \le K \le 1\,000\,000~) και το ~K~ είναι το πολύ ο αριθμός των φίλων σας που έχουν βαθμολογία σε αυτό το σημείο.

Μπορείτε να υποθέσετε ότι δεν θα υπάρξουν ίδιες βαθμολογίες στην είσοδο.

Έξοδος

Για κάθε γραμμή της εισόδου της μορφής ~Q~ ~K~, θα εκτυπώσετε μία γραμμή που θα περιέχει το αναγνωριστικό του ~K~-οστου υψηλότερα βαθμολογημένου ατόμου στη βάση δεδομένων σε εκείνο το σημείο. Σημειώστε ότι όταν ~K = 1~, αυτό είναι το άτομο με την υψηλότερη βαθμολογία και ~K = 2~ είναι το άτομο με την δεύτερη υψηλότερη βαθμολογία, κοκ.

Παράδειγμα

input

7
N 10 1000
N 3 1014
Q 1
M 10 2000
Q 1
N 65 1950
Q 2

output

3
10
65