P8045 [COCI 2015/2016 #4] HAN

Han 不想单独学习，所以他邀请他的朋友 Dominik 过来。他们一起学习了一个晚上之后，Dominik 回家了。令他吃惊的是，一名警察拦住了他，认为他**喝醉了**。众所周知，在这种情况下，通过解决一系列精心设计的任务，测试一个人的认知能力，可以证明他是否清醒。如果我们能相信 Dominik，对话将会是这样的—— > 警察：从简单点的问题开始吧……冒泡排序的复杂度是多少？ Dominik：太简单了，$\mathcal O(n^2)$。 警察：很好，下一题。请倒着念英文字母表。 Dominik：太无聊了，$\texttt{zyxwvutsrqponmlkjihgfedcba}$。 警察：你这显然是背的，不算数。再来考你一题吧。想象一下，英文字母表中的从 $\texttt{a}$ 到 $\texttt{z}$ 的所有字母以顺时针顺次排列成一个环。初始时，你从字母 $\texttt{a}$ 开始，顺时针念字母。每念完一个字母，我可以告诉你按照相反方向念字母，或者询问你到目前为止某个字母你念了多少次。准备好了吗？开始！ Dominik：唔……$\texttt{a}$、$\texttt{b}$、$\texttt{c}$…… 警察的最后一个问题显然难倒了 Dominik。现在，请你帮助 Dominik 回答这些问题。

具体地，警察在接下来将会发出 $q$ 次命令，每次命令为以下两种命令中的一种： - $\bf SMJER~n$：在 Dominik 说完第 $n$ 个字母之后，他必须开始按照与当前方向相反的方向念字母。 - $\bf UPIT~n~x$：Dominik 需要回答在他念的前 $n$ 个字母中，字母 $x$ 出现了多少次。 你需要对于每次 $\bf UPIT~n~x$ 命令输出答案。

第一行一个整数 $q$，表示警察发出的命令数。 随后 $q$ 行，描述 $q$ 次命令。每行先输入一个字符串 $s$ 和一个整数 $n$。如果 $s$ 是 $\bf UPIT$，则在输入完一个整数 $n$ 之后还需要输入一个字符 $x$。 数据保证对于所有 $q$ 次命令，$n$ 严格递增。形式化地说，$\forall i\in [1,q)$，$n_i

对于每次 $\bf UPIT~n~x$ 命令，输出一行一个整数，表示在 Dominik 说的前 $n$ 个字母中，字符 $x$ 出现的次数。

**【样例 1 解释】** Dominik 说的前 $10$ 个字母依次是：$\texttt{a}$，$\texttt{b}$，$\texttt{c}$，$\texttt{d}$，$\texttt{c}$，$\texttt{b}$，$\texttt{a}$，$\texttt{z}$，$\texttt{y}$，$\texttt{x}$。 **【样例 2 解释】** Dominik 说的前 $7$ 个字母依次是：$\texttt{a}$，$\texttt{z}$，$\texttt{a}$，$\texttt{z}$，$\texttt{y}$，$\texttt{x}$，$\texttt{w}$。 **【数据范围】** 对于 $40\%$ 的数据，保证 $n\leqslant 1000$。 对于 $60\%$ 的数据，保证 $n\leqslant 10^5$。 对于所有数据，$1\leqslant q\leqslant 10^5$，$1\leqslant n\leqslant 10^9$，$x$ 仅包含小写字母。 **【题目来源】** 本题来源自 **_[COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST 4](https://hsin.hr/coci/archive/2015_2016/contest4_tasks.pdf) T2 HAN_**，按照原题数据配置，满分 $80$ 分。 由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。