Direction Reversal and Frequency Queries

Dominik is reciting letters from the English alphabet (using the cyclic order A, B, C, …, Z) and the police issue a sequence of q commands. Initially, he recites letters in the forward direction (i.e. A, B, C, …). There are two types of commands:

• SMJER n: After Dominik recites the n^th letter, he must reverse his current direction. (If he was reciting forward then he starts reciting backward, and vice versa.)
• UPIT n x: Dominik must answer how many times the letter x appears in the first n letters he recited.

Your task is to process these q commands in order and output the answer for every UPIT command.

Note: Since the alphabet is cyclic, after 'Z' comes 'A' and before 'A' comes 'Z'. Also, if there are multiple reversal commands at the same letter index, flip the direction for each command (an even number of flips means no net change).

The problem involves simulating the recitation process and then answering the frequency queries accordingly.

inputFormat

The first line of input contains a single integer q (q > 0), representing the number of commands.

Each of the following q lines contains a command in one of the two formats:

• SMJER n — reversal command. n is a positive integer indicating that after the n^th letter, the reading direction reverses.
• UPIT n x — query command. n is a positive integer and x is an uppercase English letter. You must output the number of times x appears among the first n letters recited.

It is guaranteed that the commands are given in the order they occur, and n in the commands does not exceed the number of letters that need to be simulated.

outputFormat

For each UPIT command, output a single integer on a new line which is the answer to the query.

sample

5
SMJER 3
UPIT 5 A
SMJER 7
UPIT 10 C
UPIT 12 Z

2
1
2