P8045 [COCI 2015/2016 #4] HAN

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.

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.

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

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.

**[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](https://hsin.hr/coci/archive/2015_2016/) [CONTEST 4](https://hsin.hr/coci/archive/2015_2016/contest4_tasks.pdf) T2 HAN_**, and according to the original testdata configuration, the full score is $80$ points. Translated and organized by [Eason_AC](https://www.luogu.com.cn/user/112917). Translated by ChatGPT 5