Kecleon

Kecleon are similar to chameleons, and their skin can change to many colors. This problem assumes that the body color of a Kecleon is one of 26 colors, each denoted by a distinct lowercase English letter.

Several Kecleon want to form a line. The line is initially empty. You have to process two types of queries.

• Type 1: A Kecleon of a given color arrives at the right end of the line and stays there forever.
• Type 2: You are given an integer k. Consider each contiguous block of k Kecleon in the line, and read its colors from left to right as a sequence. Count how many of these sequences are exactly the same as the sequence of colors of the first k Kecleon in the line.

You do not know in advance the order in which the Kecleon will join the line, so the queries must be processed online.

The input is encoded. Keep a variable last that is initially 0. After each query of type get, set last to the answer you just computed.

The first line contains an integer q (2 ≤ q ≤ 300 000), the number of queries.

Each of the next q lines describes one query in one of the following formats.

• add ci′ (ci′ is a lowercase English letter): Let ci = char((asc(ci′) + last) mod 26), where asc(x) is the 0-based index of letter x in the alphabet and char(x) is the letter at 0-based index x. This adds a Kecleon of color ci to the right end of the line.
• get ki′ (1 ≤ ki′ ≤ n): Let n be the number of Kecleon currently in the line. Let ki = ((ki′ − 1 + last) mod n) + 1. Find how many intervals of length ki have the same color sequence as the first ki Kecleon in the line.

It is guaranteed that the first query is of type add and that there is at least one query of type get.

For each query of type get, print the answer on its own line.

In this example, the Kecleon join the line in the order abcababca. The decoded values of k are 1, 3, 2, 1, 2, 3, and 4.

Assume that 'a' = , 'b' = , and 'c' = . The exact order of the queries is shown here: