Han

Ο Han δεν ήθελε να σπουδάσει μόνος, έτσι κάλεσε τον φίλο του Dominik να έρθει. Μετά από μια γεμάτη περιπέτεια βραδιά που θα μείνει αξέχαστη για έναν αριθμό ρεκόρ λυμένων εργασιών από τον τομέα των ηλεκτρονικών, ο Dominik πήγε σπίτι του. Προς έκπληξή του, η αστυνομία τον σταμάτησε νομίζοντας ότι ήταν μεθυσμένος. Είναι γνωστό ότι σε αυτές τις περιπτώσεις η νηφαλιότητα αποδεικνύεται με την επίλυση μιας σειράς προσεκτικά κατασκευασμένων εργασιών που δοκιμάζουν τις γνωστικές ικανότητες ενός άνδρα. Αν μπορούμε να εμπιστευτούμε τον Dominik, η συζήτηση πήγε κάπως έτσι:
Αστυνομικός: Κάτι εύκολο για αρχή... Ποια είναι η πολυπλοκότητα της ταξινόμησης με φυσαλίδες;
Dominik: Αυτό είναι πολύ εύκολο, ~O(n^2)~.
Αστυνομικός: Πείτε το αγγλικό αλφάβητο αντίστροφα.
Dominik: Trivial, zyxwvutsrqponmlkjihgfedcba
Αστυνομικός: Το έμαθες απ'έξω. Τώρα φανταστείτε ότι όλα τα γράμματα του αγγλικού αλφαβήτου από το "a" έως το "z" είναι γραμμένα αντίστοιχα δεξιόστροφα σε κύκλο. Ξεκινήστε με το γράμμα "a" και πείτε τα γράμματα δεξιόστροφα. Μετά από κάθε προφορικό γράμμα, μπορώ να σας πω να συνεχίσετε να λέτε το αλφάβητο με αντίστροφη σειρά ή μπορώ να σας ρωτήσω πόσες φορές μέχρι τώρα έχετε πει ένα συγκεκριμένο γράμμα. Είσαι έτοιμος? ~3,\;2,\;1~, ξεκίνα!
Dominik: Χμ... ~a,\;b,\;c\ldots~
Γράψτε ένα πρόγραμμα που λύνει το πρόβλημα του Dominik.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο αριθμό ~Q\;(1 \leq Q \leq 100\,000)~, τον αριθμό των εντολών του αστυνομικού. Κάθε μία από τις ακόλουθες ~Q~ γραμμές περιέχει μία από τις εντολές του αστυνομικού με τη μορφή "SMJER n" (Κροατικά για κατεύθυνση) ή "UPIT n x" (Κροατικά για ερώτηση). Η σειρά με τη μορφή "SMJER n" σημαίνει ότι, μετά το ~n~-οστό προφορικό γράμμα, ο Dominik πρέπει να αρχίσει να λέει το αλφάβητο αντίστροφα, ενώ η σειρά με τη μορφή "UPIT n x" σημαίνει ότι ο Dominik πρέπει να πει πόσες φορές μέχρι τώρα είπε το γράμμα ~x~ στα πρώτα ~n~ προφορικά γράμματα.

Η εντολή του αστυνομικού θα δίνεται χρονολογικά στην είσοδο ή, οι αριθμοί ~n\;(1 \leq n \leq 10^9)~ από τις εντολές θα είναι αυστηρά αύξοντες. Ο χαρακτήρας ~x~ από τη σειρά με τη μορφή "UPIT n x" είναι ένα πεζό γράμμα του αγγλικού αλφαβήτου.

Έξοδος

Για κάθε παραγγελία με τη μορφή "UPIT n x", τυπώστε πόσες φορές ο Dominik έχει πει το γράμμα ~x~ στα πρώτα ~n~ προφορικά γράμματα. Η απάντηση σε κάθε ερώτημα πρέπει να γραφτεί σε ξεχωριστή γραμμή και τα ερωτήματα πρέπει να απαντηθούν με τη σειρά που δίνεται στην είσοδο.

Βαθμολογία

Σε περιπτώσεις δοκιμών αξίας ~40~% των συνολικών πόντων, θα ισχύει επιπλέον: ~N \leq 1000~.
Σε περιπτώσεις δοκιμών αξίας ~60~% των συνολικών πόντων, θα ισχύει επιπλέον: ~N \leq 10^5~ .

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

input

5
UPIT 1 b
UPIT 3 b
SMJER 4
UPIT 7 a
UPIT 10 z

output

0
1
2
1

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

Ο Dominik λέει τα ακόλουθα γράμματα: ~a,\;b,\;c,\;d,\;c,\;b,\;a,\;z,\;y,\;x~.

input

5
SMJER 1
SMJER 2
SMJER 3
UPIT 5 a
UPIT 7 w

output

2
1

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

Ο Dominik λέει τα ακόλουθα γράμματα: ~a,\;z,\;a,\;z,\;y,\;x,\;w~.

input

4
UPIT 100 a
UPIT 200 c
UPIT 300 a
UPIT 400 b

output

4
8
12
16