Description

具体地，警察在接下来将会发出 $q$ 次命令，每次命令为以下两种命令中的一种：

• $\bf SMJER~n$：在 Dominik 说完第 $n$ 个字母之后，他必须开始按照与当前方向相反的方向念字母。
• $\bf UPIT~n~x$：Dominik 需要回答在他念的前 $n$ 个字母中，字母 $x$ 出现了多少次。

你需要对于每次 $\bf UPIT~n~x$ 命令输出答案。

Input Format

第一行一个整数 $q$，表示警察发出的命令数。
随后 $q$ 行，描述 $q$ 次命令。每行先输入一个字符串 $s$ 和一个整数 $n$。如果 $s$ 是 $\bf UPIT$，则在输入完一个整数 $n$ 之后还需要输入一个字符 $x$。

数据保证对于所有 $q$ 次命令，$n$ 严格递增。形式化地说，$\forall i\in [1,q)$，$n_i<n_{i+1}$。

Output Format

对于每次 $\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

Hint

【样例 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 翻译整理提供。