Tourney

Ο Don Cherry προσλήφθηκε για να εκτελεί ~24~-ωρη κάλυψη μιας σειράς τουρνουά αποσυναρμολόγησης επίπλων μεμονωμένων αποκλεισμών, τύπου bracket. Κάθε διαγωνιζόμενος έχει μια επίπεδο ικανότητας αποσυναρμολόγησης επίπλων, έναν ακέραιο αριθμό μεταξύ του ~1~ και το ~1\,000\,000\,000~. Σε κάθε αγώνα head-to-head, ο διαγωνιζόμενος με το μεγαλύτερο επίπεδο δεξιοτήτων κερδίζει και προχωρά, ενώ ο άλλος αποβάλλεται από το τουρνουά. Είναι εγγυημένο ότι, ανά πάσα στιγμή, τα επίπεδα δεξιοτήτων όλων των διαγωνιζομένων είναι διαφορετικά, επομένως δεν υπάρχουν ισοπαλίες.

Υπάρχουν ~2_N~ (~1 \le N \le 20~) θέσεις διαγωνιζομένων στο δέντρο του τουρνουά, αριθμημένες με ~1, 2, ... , 2^N~ από αριστερά προς τα δεξιά. Στον πρώτο γύρο, οι διαγωνιζόμενοι ~1~ και ~2~ αντιμετωπίζει ο ένας τον άλλον σε έναν αγώνα αποσυναρμολόγησης επίπλων, όπως και οι διαγωνιζόμενοι ~3~ και ~4~ κ.λπ. Σε κάθε επόμενο γύρο, οι νικητές των δύο πρώτων αγώνων από τον προηγούμενο γύρο διαγωνίζονται, όπως και οι νικητές των δύο επόμενων, κ.λπ. Μετά από ~N~ γύρους, ένας μόνο νικητής παραμένει. Για παράδειγμα, όταν ~N = 2~, το δέντρο του τουρνουά μοιάζει με αυτό:

Όπου το ~A~ αντιπροσωπεύει τον νικητή του αγώνα μεταξύ των διαγωνιζόμενων ~1~ και ~2~, το ~B~ αντιπροσωπεύει τον νικητή του αγώνα μεταξύ των διαγωνιζόμενων ~3~ και ~4~ και το ~C~ αντιπροσωπεύει τον νικητή του αγώνα μεταξύ του ~A~ και του ~B~. Ο νικητής αυτού του τουρνουά είναι ο ~C~.

Λόγω των συμβολαίων με χορηγούς, κάποιοι διαγωνιζόμενοι θα αντικατασταθούν με τον χρόνο. Αφού έρθει κάποιο νέο άτομο, γίνεται ένα νέο τουρνουά.

Για να βοηθήσετε τον Don Cherry, πρέπει να γράψετε ένα πρόγραμμα για να υπολογίσετε ορισμένες στατιστικές των τουρνουά σε διάφορες χρονικές στιγμές, δεδομένης μίας ακολουθίας από ~M~ (~1 \le M \le 1\,000\,000~) εντολές - δείτε τη μορφή της εισόδου παρακάτω.

Είσοδος

Η πρώτη γραμμή της εισόδου περιέχει δύο ακέραιους, ~N~ (~1 \le N \le 20~) και ~M~ (~1 \le M \le 1\,000\,000~), χωρισμένους με ένα κενό.

Οι επόμενες ~2^N~ γραμμές, για ~i~ από το ~1~ έως το ~2^N~, καθεμία περιέχει έναν ακέραιο ~S_i~, που υποδυκνύουν το επίπεδο δεξιότητας του αρχικού διαγωνιζόμενου στη θέση ~i~ στο δέντρο του τουρνουά.

Καθεμία από τις ακόλουθες ~M~ γραμμές θα είναι μία εντολή με μια από τρεις μορφές:

• "~R~ ~i~ ~S~" σημαίνει ότι ο διαγωνιζόμενος στη θέση ~i~ αφαιρείται και αντικαθίσταται με έναν νέο με επίπεδο δεξιότητας ~S~. Ένα νέο τουρνουά ξεκινά έπειτα.

• "~W~" σημαίνει ότι το πρόγραμμά σας θα πρέπει να καθορίσει ποιός κέρδισε στο τρέχων τουρνουά. Εκτυπώστε τη θέση ~i~ (μεταξύ ~1~ και ~2^N~) αυτού του διαγωνιζόμενου.

• "~S~ ~i~" σημαίνει ότι το πρόγραμμά σας θα πρέπει να εκτυπώσει τον αριθμό των γύρων που ο διαγωνιζόμενο στη θέση ~i~ κέρδισε στο τρέχων τουρνουά.

Έξοδος

Για κάθε "~W~" ή "~S~ ~i~" εντολή στην είσοδο, εκτυπώστε τον αντίστοιχο ακέραιο σε μία γραμμή μόνο του.

Παράδειγμα

input

2 8
30
20
10
40
S 1
W
R 4 9
S 4
W
R 2 35
S 2
W

output

1
4
0
1
2
2

Επεξήγηση του παραδείγματος

Τα αποτελέσματα του πρώτου τουρνουά είναι τα εξής:

Όπως φαίνεται, ο διαγωνιζόμενος ~1~ κερδίζει τον αγώνα ~1~ και ο διαγωνιζόμενος ~4~ κερδίζει το τουρνουά. Μετά από αυτό, ο διαγωνιζόμενος ~4~ αντικαθίσταται από ένα καινούριο διαγωνιζόμενο με επίπεδο δεξιότητας ~9~. Όπως φαίνεται παρακάτω, αυτό προκαλεί ένα διαφορετικό αποτέλεσμα για το τουρνουά που γίνεται μετά την τρίτη εντολή:

Τέλος, η κατάσταση του δέντρου του τουρνουά μετά την επόμενη αντικατάσταση διαγωνιζόμενου (που προκάλεσε η έκτη εντολή) είναι: