Problem Background

Han doesn't want to study alone, so he invites his friend Dominik over. After studying together for a night, Dominik goes home. To his surprise, a police officer stops him, suspecting he is drunk. It is well known that in such situations, one can prove their sobriety by solving a series of carefully designed tasks that test cognitive abilities. If we can trust Dominik, the conversation would go like this—

Police: Let's start with a simple question... What is the complexity of bubble sort?
Dominik: Too easy, $\mathcal O(n^2)$.
Police: Good, next question. Please recite the English alphabet backwards.
Dominik: Too boring, $\texttt{zyxwvutsrqponmlkjihgfedcba}$.
Police: You're clearly memorizing that, it doesn't count. Let's test you with another question. Imagine all the letters from $\texttt{a}$ to $\texttt{z}$ arranged in a clockwise circle. Initially, you start from letter $\texttt{a}$ and recite the letters clockwise. After each letter, I can tell you to recite in the opposite direction or ask you how many times you've recited a certain letter so far. Ready? Start!
Dominik: Hmm... $\texttt{a}$, $\texttt{b}$, $\texttt{c}$...

The police officer's last question clearly stumped Dominik. Now, please help Dominik answer these questions.

Problem Description

Specifically, the police officer will issue $q$ commands, each being one of the following types:

• $\bf SMJER~n$: After Dominik recites the $n$-th letter, he must start reciting in the opposite direction.
• $\bf UPIT~n~x$: Dominik needs to answer how many times the letter $x$ has appeared in the first $n$ letters he recited.

You need to output the answer for each $\bf UPIT~n~x$ command.

Input Format

The first line contains an integer $q$, the number of commands issued by the police officer.
The next $q$ lines describe the commands. Each line starts with a string $s$ and an integer $n$. If $s$ is $\bf$, an additional character $x$ follows the integer $n$.

It is guaranteed that for all $q$ commands, $n$ strictly increases. Formally, $\forall i \in [1, q)$, $n_i < n_{i+1}$.

Output Format

For each $\bf UPIT~n~x$ command, output a single line containing an integer, the number of times the character $x$ appears in the first $n$ letters recited by Dominik.

Sample Input and Output

Input Sample #1

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

Output Sample #1

0
1
2
1

Input Sample #2

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

Output Sample #2

2
1

Input Sample #3

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

Output Sample #3

4
8
12
16

Notes/Hints

[Sample 1 Explanation]

The first 10 letters recited by Dominik are: $\texttt{a}$, $\texttt{b}$, $\texttt{c}$, $\texttt{d}$, $\texttt{c}$, $\texttt{b}$, $\texttt{a}$, $\texttt{z}$, $\texttt{y}$, $\texttt{x}$.

[Sample 2 Explanation]

The first 7 letters recited by Dominik are: $\texttt{a}$, $\texttt{z}$, $\texttt{a}$, $\texttt{z}$, $\texttt{y}$, $\texttt{x}$, $\texttt{w}$.

[Data Range]

For 40% of the data, $n \leq 1000$.
For 60% of the data, $n \leq 10^5$.
For all data, $1 \leq q \leq 10^5$, $1 \leq n \leq 10^9$, $x$ is a lowercase letter.

[Problem Source]

This problem is from COCI 2015-2016 CONTEST 4 T2 HAN, configured with the original data, with a full score of $80$ points.

Provided by Eason_AC for translation and arrangement.

见题面 Input 部分

见题面 Output 部分