Background

Problem Description

Let $S_0=\varnothing$. Maintain a data structure that supports the following operations:

• 1 hoc s: Let $S_i=S_{hoc}\cup\{s\}$, where $s$ is a string (it is guaranteed that before the operation $s\notin S_{hoc}$).
• 2 hoc s: Let $S_i=S_{hoc}$, and query the sum of the number of occurrences of all strings in $S_i$ within the given string $s$.

Input Format

The first line contains a positive integer $q$, indicating the number of queries.

The next $q$ lines each contain one operation, in the format described above.

Output Format

For each operation 2, output one line containing the answer.

5
1 0 abc
2 0 abc
1 2 def
2 3 defg
2 1 abcd

0
1
1

Hint

Sample Explanation

In the third line, we ask how many times the strings in version $0$ appear in abc. Since version $0$ is empty, it appears $0$ times.

In the fifth line, we ask how many times the strings in version $3$ appear in defg. Since version $3$ contains the string def, it appears $1$ time.

In the sixth line, we ask how many times the strings in version $1$ appear in abcd. Since version $1$ contains the string abc, it appears $1$ time.

Constraints and Notes

"This problem uses bundled testdata."

• $\texttt{Subtask 1(10 pts):} \displaystyle \sum|s_i|\le 1000$.
• $\texttt{Subtask 2(20 pts):}$ All added strings have the same length.
• $\texttt{Subtask 3(20 pts):}$ All added strings contain only one kind of character.
• $\texttt{Subtask 4(20 pts):}q\le 10^3$.
• $\texttt{Subtask 5(30 pts):}$ No special restrictions.

For all testdata, $1\le q\le 5\times 10^5$, $\displaystyle 1\le \sum_i|s_i|\le 10^6$. All strings contain only lowercase letters.

Translated by ChatGPT 5