Deda

Η μικρή Marica φτιάχνει ένα ανόητο ασυνήθιστο παραμύθι και το διηγείται στον παππού της που τη διακόπτει συνέχεια και της κάνει ηλίθιες ενδιαφέρουσες ερωτήσεις.

Στο παραμύθι της Marica, ~N~ παιδιά, που συμβολίζονται με αριθμούς από το 1 έως το ~N~ από την ηλικία τους (από το μικρότερο που συμβολίζεται με 1, μέχρι το μεγαλύτερο που συμβολίζεται με ~N~), ξεκίνησαν μια βόλτα με το τρένο. Το τρένο φεύγει από το σταθμό 0 και σταματά με σειρά στους σταθμούς ~1,\;2,\;3,\;\ldots~, έως το άπειρο.

Κάθε μία από τις ακόλουθες δηλώσεις της Marica έχει τη μορφή: "Στη στάση ~X~​, το παιδί ~A~ βγήκε έξω", όπου η σειρά αυτών των δηλώσεων είναι εντελώς αυθαίρετη. Με άλλα λόγια, δεν εξαρτάται από τον αριθμό του σταθμού. Ο παππούς της κάνει μερικές φορές μια ερώτηση της μορφής: "Με βάση τις μέχρι στιγμής δηλώσεις, από τα παιδιά που συμβολίζονται με αριθμό μεγαλύτερο ή ίσο του ~B~, ποιο είναι το μικρότερο παιδί που ήταν στο τρένο για ~Y~ ή λιγότερες στάσεις;". Αν τη στιγμή που ο παππούς κάνει την ερώτηση δεν έχει ειπωθεί μέχρι στιγμής ότι ένα παιδί κατεβαίνει από το τρένο, υποθέτουμε ότι το παιδί είναι στο τρένο για άπειρο αριθμό στάσεων.

Η Marica πρέπει να απαντήσει σωστά σε κάθε ερώτηση του παππού της, διαφορετικά ο παππούς θα θυμώσει και θα κοιμηθεί. Η απάντηση πρέπει να είναι σωστή τη στιγμή που ο παππούς κάνει την ερώτηση, ενώ μπορεί να αλλάξει αργότερα με βάση τις νέες δηλώσεις της Marica, αλλά αυτό δεν έχει σημασία. Γράψτε ένα πρόγραμμα που παρακολουθεί τις δηλώσεις της Marica και απαντά στις ερωτήσεις του παππού της.

Είσοδος

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

• είτε η δήλωση της Marica της μορφής "~M~" ~X\;A~​, όπου το "~M~" υποδηλώνει Marica, και ~X~ και ~A~ είναι θετικοί ακέραιοι αριθμοί​~(1 \le X \le 1\,000\,000\,000,\;1 \le A \le N)~ από την περιγραφή εργασίας,
• ή το ερώτημα του παππού της για τη μορφή "~D~" ~Y\;B~, όπου το "~D~" υποδηλώνει τον παππού, και ~Y~ και ~B~ είναι θετικοί ακέραιοι ~(1 \le Y \le 1\,000\,000,\;1 \le B \le N)~ από την περιγραφή εργασίας.
  Όλες οι δηλώσεις της Marica αντιστοιχούν σε διαφορετικά παιδιά και τουλάχιστον μια γραμμή στην εισαγωγή είναι η ερώτηση του παππού της.

Έξοδος

Για την κάθε ερώτηση του παππού, πληκτρολογήστε τον αριθμό που απαιτείται για το παιδί στη δική του γραμμή. Εάν δεν υπάρχει τέτοιο παιδί, τυπώστε -1.

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

input

3 4
M 10 3
M 5 1
D 20 2
D 5 1

output

3
1

input

10 10
M 20 10
D 1 9
M 2 3
D 17 10
M 20 2
D 8 2
M 40 1
D25 2
M 33 9
D 37 9

output

-1
-1
3
2
9