Han 不想独自学习，于是他邀请了他的朋友 Dominik 来家里。在度过了一个因解决了创纪录数量的电子学任务而令人难忘的夜晚后，Dominik 回家了。令他惊讶的是，警察拦住了他，怀疑他酒后驾驶。众所周知，在这种情况下，需要通过解决一系列精心设计的、测试人类认知能力的测试来证明清醒。如果 Dominik 的话可信，他们的对话大致如下：

警察：先来点简单的……冒泡排序的时间复杂度是多少？

Dominik：这太简单了，$O(n^2)$。

警察：倒着背诵英文字母表。

Dominik：轻而易举，zyxwvutsrqponmlkjihgfedcba。

警察：你这是死记硬背的。现在，想象英文字母表中的所有字母从 'a' 到 'z' 顺时针排成一个圆圈。从字母 'a' 开始，顺时针说出这些字母。在你说出每个字母后，我可能会让你开始逆序说字母，或者问你到目前为止你已经说出了多少次某个特定的字母。准备好了吗？3，2，1，开始！

Dominik：呃…… a, b, c……

写一个程序来解决 Dominik 的问题。

输入格式

第一行包含一个整数 $Q$ ($1 \le Q \le 100\,000$)，表示警察指令的数量。

接下来的 $Q$ 行，每行包含一个警察的指令，格式为 “SMJER n”（克罗地亚语中意为“方向”）或 “UPIT n x”（克罗地亚语中意为“查询”）。格式为 “SMJER n” 的指令意味着在说出第 $n$ 个字母后，Dominik 必须开始逆序说字母；而格式为 “UPIT n x” 的指令意味着 Dominik 必须回答在说出的前 $n$ 个字母中，他已经说出了多少次字母 $x$。

警察的指令在输入中按时间顺序给出，也就是说，指令中的数字 $n$ ($1 \le n \le 10^9$) 是严格递增的。格式为 “UPIT n x” 的指令中的字符 $x$ 是一个英文小写字母。

输出格式

对于每个格式为 “UPIT n x” 的指令，输出在前 $n$ 个说出的字母中，Dominik 说出字母 $x$ 的次数。每个查询的答案需要写在单独的一行中，并且查询需要按照输入中给出的顺序进行回答。

子任务

在占总分 40% 的测试数据中，还满足：$n \le 1000$。

在占总分 60% 的测试数据中，还满足：$n \le 10^5$。

样例

输入样例 1

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

输出样例 1

0
1
2
1

输入样例 2

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

输出样例 2

2
1

输入样例 3

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

输出样例 3

4
8
12
16

说明

第一个样例的解释：Dominik 说出的字母依次为：a, b, c, d, c, b, a, z, y, x。

第二个样例的解释：Dominik 说出的字母依次为：a, z, a, z, y, x, w。