题目背景

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<n_{i+1}$。

输出格式

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

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

提示

【样例 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 CONTEST 4 T2 HAN，按照原题数据配置，满分 $80$ 分。

由 Eason_AC 翻译整理提供。