Description

You need to perform three types of operations on a string: 0. Insert a string $y_i$ at position $x_i$.

1. Delete the substring in the interval $[x_i, y_i)$.
2. Query how many times a given substring $z_i$ occurs in the substring of the interval $[x_i, y_i)$.

The indices of the string start from $0$ (that is, the first character has index $0$).

Initially, the string is empty.

For the insertion operation, after insertion the first character of $y_i$ should have index $x_i$. For the deletion operation, the interval $[x_i, y_i)$ is a left-closed, right-open interval. For the query operation, the interval $[x_i, y_i)$ is a left-closed, right-open interval.

All inserted strings and query strings are non-empty and contain only characters $\texttt{0}\sim\texttt{9}$.

All query intervals and deletion intervals are non-empty.

The input is guaranteed to be valid.

If you do not understand the term "left-closed, right-open interval", please see the sample explanation.

Input Format

The first line contains an integer $T$, the number of operations.

In the following $T$ lines, the first number $p_i$ indicates the type of the operation:

• If $p_i=0$, then an integer $x_i$ and a string $y_i$ follow, indicating an insertion.
• If $p_i=1$, then two integers $x_i$ and $y_i$ follow, indicating a deletion.
• If $p_i=2$, then two integers $x_i$ and $y_i$, and a string $z_i$ follow, indicating a query.

Output Format

For each query operation, output one line with the answer to that query.

8
0 0 894894894
2 0 2 894
2 0 9 894
0 2 6
2 0 9 64
2 0 9 894
1 2 6
2 0 6 894

0
3
1
1
2

Hint

Sample explanation:

• After the first operation, the string is $\texttt{894894894}$.
• In the second operation, the queried interval is $\texttt{89}$, which contains no $\texttt{894}$.
• In the third operation, the queried interval is $\texttt{894894894}$, which contains three $\texttt{894}$.
• After the fourth operation, the string is $\texttt{8964894894}$.
• In the fifth operation, the queried interval is $\texttt{896489489}$, which contains one $\texttt{64}$.
• In the sixth operation, the queried interval is $\texttt{896489489}$, which contains one $\texttt{894}$.
• After the seventh operation, the string is $\texttt{894894}$.
• In the eighth operation, the queried interval is $\texttt{894894}$, which contains two $\texttt{894}$.

Constraints:

• In $50\%$ of the testdata, the number of queries $\le 100$ (not the number of operations).
• In $100\%$ of the testdata, the total inserted length $\le 2\times 10^6$, the string length at any time $\le 10^6$, the number of insertions $\le 1001$, the number of deletions $\le 1000$, and the total length of all queried $z_i$ $\le 10^4$.

Source: 2012 CTT internal contest, by gyz.

Translated by ChatGPT 5