Background

Han did not want to study alone, so he invited his friend Dominik over. After they studied together for an evening, Dominik went home. To his surprise, a police officer stopped him and believed that he was drunk. As everyone knows, in this situation, by solving a series of carefully designed tasks to test a person’s cognitive ability, one can prove whether they are sober. If we can trust Dominik, the conversation would go like this—

Police officer: Let’s start with an easy question... What is the complexity of bubble sort?
Dominik: Too easy, $\mathcal O(n^2)$.
Police officer: Very good, next question. Please recite the English alphabet backwards.
Dominik: Too boring, $\texttt{zyxwvutsrqponmlkjihgfedcba}$.
Police officer: You clearly memorized that, it does not count. Let me test you with another question. Imagine that all letters from $\texttt{a}$ to $\texttt{z}$ are placed clockwise in order on a circle. Initially, you start from the letter $\texttt{a}$ and read letters clockwise. After you finish reading each letter, I can tell you to read in the opposite direction, or I can ask how many times you have read a certain letter so far. Ready? Start!
Dominik: Uh... $\texttt{a}$, $\texttt{b}$, $\texttt{c}$...

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

Problem Description

Specifically, the police officer will give $q$ commands. Each command is one of the following two types:

• $\bf SMJER~n$: After Dominik says the $n$-th letter, he must start reading letters in the opposite direction to the current one.
• $\bf UPIT~n~x$: Dominik needs to answer how many times the letter $x$ appears among the first $n$ letters he has said.

For each $\bf UPIT~n~x$ command, output the answer.

Input Format

The first line contains an integer $q$, which is the number of commands given by the police officer.
Then follow $q$ lines describing the $q$ commands. Each line first contains a string $s$ and an integer $n$. If $s$ is $\bf UPIT$, then after the integer $n$ you also need to input a character $x$.

The testdata guarantees that for all $q$ commands, $n$ is strictly increasing. Formally, $\forall i\in [1,q)$, $n_i<n_{i+1}$.

Output Format

For each $\bf UPIT~n~x$ command, output one line with an integer, which is the number of times the character $x$ appears among the first $n$ letters Dominik has said.

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

0
1
2
1

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

2
1

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

4
8
12
16

Hint

[Sample 1 Explanation]

The first $10$ letters Dominik says, in order, 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 Dominik says, in order, are: $\texttt{a}$, $\texttt{z}$, $\texttt{a}$, $\texttt{z}$, $\texttt{y}$, $\texttt{x}$, $\texttt{w}$.

[Constraints]

For $40\%$ of the testdata, $n\leqslant 1000$.
For $60\%$ of the testdata, $n\leqslant 10^5$.
For all testdata, $1\leqslant q\leqslant 10^5$, $1\leqslant n\leqslant 10^9$, and $x$ contains only lowercase letters.

[Source]

This problem is from COCI 2015-2016 CONTEST 4 T2 HAN, and according to the original testdata configuration, the full score is $80$ points.

Translated and organized by Eason_AC.

Translated by ChatGPT 5