• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۶۴ مگابایت

---

Saeed didn’t want to study solo so he invited his friend Pouya to come over. After an eventful evening that will be remembered for a record number of solved tasks from the field of electronics, Pouya went home. To his surprise, the police stopped him thinking he was drunk! It is known that in these situations sobriety is proven by solving a series of carefully crafted tasks that test a man’s cognitive abilities. If we can trust Pouya, the conversation went something like this:

Policeman: Say the English alphabet in reverse.

Pouya: Trivial, zyxwvutsrqponmlkjihgfedcba

Policeman: You learned that by heart. Now imagine that all the letters of the English alphabet from 'a’ to ‘z’ are respectively written clockwise in a circle. Begin with the letter ‘a’ and say the letters clockwise. After each spoken letter, I can tell you to continue saying the alphabet in reverse order or I can ask you how many times so far you’ve said a certain letter. Are you ready? 3, 2, 1, Go!

Pouya: Um... a, b, c ...

Write a program that solves Pouya’s problem.

Input

The first line of input contains the integer Q, the number of policeman’s orders.

Each of the following Q lines contains one of the policeman’s order in the form of “Change n” or “Query n x”. The order in the form “Change n” means that, after the n-th spoken letter, Pouya must start saying the alphabet in reverse, whereas the order in the form “Query n x” means that Pouya must say how many times so far he’s said the letter x in the first n spoken letters.

The policeman’s order will be given chronologically in the input, or, the numbers n from the orders will be strictly ascending. The character x from the order in the form of “Query n x” is a lowercase letter of the English alphabet.

Output

For each order in the form of “Query n x”, output how many times Pouya has said the letter x in the first n spoken letters. The answer to each query needs to be written in a separate line, and the queries need to be answered in the order given in the input.

Constraints

• $1 \leq Q \leq 10^5 $
• $1 \leq n \leq 10^9 $

Sample Test Data

input 1

5
Change 1
Change 2
Change 3
Query 5 a
Query 7 w

output 1

1

input 2

5
Query 100 a
Query 200 c
Query 300 a
Query 400 b

output 2

4
8
12
16