Do you know how Kecleon looks? Similar to chameleons, its skin can be colored in various ways and this is what this task is about. For the purposes of this problem, let's assume that the body of Kecleon is colored in one out of $$$26$$$ different colors, each denoted by a distinct lowercase English character.
Multiple Kecleon want to form a line, which is initially empty. You have to process two types of queries:
- In the first type, a Kecleon of a specified color comes to the right end of the line and remains there forever.
- In the second type, you're given an integer $$$k$$$. For each contiguous interval of $$$k$$$ specimens in the line, consider the sequence of colors of Kecleon in this interval, from left to right. You have to say how many of these sequences are exactly the same as the sequence of colors of the first $$$k$$$ Kecleon in the line.
Unfortunately, Kecleon still don't know the order in which they will join the line. Therefore, you need to process the queries online.
The input is encoded. In order to decode the queries, you need to maintain a variable last which is initially equal to $$$0$$$. After each query of the second type, the value of last is set to the most recently computed answer.
The first line contains one integer $$$q$$$ ($$$2 \leq q \leq 300\,000$$$) — the number of queries in the input.
Each of the next $$$q$$$ lines contains a description of one query. Each is in one of the following formats:
- add $$$c_i'$$$ ($$$c_i'$$$ is a lowercase English letter) — Let $$$c_i=char((asc(c_i')+\mathtt{last})\mod{26})$$$ where $$$asc(x)$$$ denotes the 0-based index of $$$x$$$ in the English alphabet, and $$$char(x)$$$ means the $$$x$$$-th character in the English alphabet (0-based as well). This operation adds a Kecleon of color $$$c_i$$$ to the right end of the line.
- get $$$k_i'$$$ ($$$1 \le k_i' \le n$$$) — Let $$$n$$$ be equal to the number of Kecleon currently in the line. Now, let $$$k_i=((k_i'-1+\mathtt{last})\mod{n})+1$$$. You need to find out how many intervals of length $$$k_i$$$ have the same sequence of colors as the first $$$k_i$$$ Kecleon in the line.
It's guaranteed that the first query has type add and that there is at least one query of type get.
For each query of type get output one line containing one integer described in the statement.
16 add a add b add c add a get 1 add z get 1 get 1 add y add z add a add y get 8 get 7 get 9 get 2
2 1 2 4 3 2 2
In this sample, Kecleon come to the line in the following order: abcababca. The decoded values $$$k_i$$$ are: $$$1$$$, $$$3$$$, $$$2$$$, $$$1$$$, $$$2$$$, $$$3$$$, and $$$4$$$.
Assume that 'a'$$$=$$$
, 'b'$$$=$$$
and 'c'$$$=$$$
. Here is the exact order of queries:
