Castle

K found a strange game on his computer. The game starts with a string $S$ of length $N$ ($1 \le N \le 1000$) and an empty set $T$. Three kinds of events happen while the game runs.

• One character is appended to the end of $S$, so the length of $S$ grows by 1.
• The current $S$ is added to the set $T$.
• The game master asks: "how many strings in $T$ are suffixes of $S$?" A suffix of $S$ is a substring that may start at any position of $S$ but must end at the last position of $S$.

K wants to visit a famous castle near his hometown, so help him finish the game as fast as possible.

The first line contains two integers $N$ and $E$. $N$ is the length of the initial string $S$, and $E$ is the number of events ($E \le 1\,200\,000$).

The second line contains the string $S$. It consists of lowercase letters a-z only.

Each of the next $E$ lines describes one event. Every such line starts with an integer $p$ giving the event type.

• If $p$ is 1, one character (a-z) follows on the same line. Append that character to the end of $S$.
• If $p$ is 2, add the current $S$ to $T$.
• If $p$ is 3, answer the question "how many strings in $T$ are suffixes of the current $S$?".

For every event of type 3 in the input, print the answer as an integer on its own line.

$T$ is a set, so adding the same string several times still leaves one copy in it.

The input is large, so fast input and output are required. In C use scanf and printf, in C++ put cin.tie(NULL); ios::sync_with_stdio(false); before reading, and in Java use BufferedReader and BufferedWriter.