Problem Description

Alice just tries to maintain a string, with a kind of operation and a kind of query.
The kind of operation allows to insert a character at the end of the string.
The kind of query considers the substring, denoted by $T$, of the string from the $l$-th character to the $r$-th one, and asks the maximum length of substring of $T$ which appears at least twice in $T$.
If no substring appears at least twice in $T$, the outcome should be $0$.

Input

The first line consists a string in lowercase and a positive integer m. We use $len$ to denote the length of this string.
Each of the following m lines consists a operation or a query.

We define a temporary variable $tmp$ and it is initially set to $0$.
We use the format "1 c" to describe the operation where $(c-'a'+tmp)~mod~26+'a'$ is the new character.
We use the format "2 l r" to describe the query where $(l-1+tmp)~mod~len+1$ and $(r-1+tmp)~mod~len+1$ are the indexes of substring $T$.
We guarantee that $1\le (l-1+tmp)~mod~len+1\le (r-1+tmp)~mod~len+1\le len$ and after this query $tmp$ should be modified to the outcome.

The initial length of the string and $m$ are no more than $50000$.

Output

For each query, out the outcome in one line.

aabda 6
2 1 4
1 a
2 1 5
1 b
2 6 5
2 7 4

1
2
3
2