Description

The Mirror Temple is a magical temple, where you can catch a glimpse of the truth in your heart.

Theo is trapped inside a mirror. When Madeline tries to save Theo, the “creatures” in the temple give her a difficult puzzle. The puzzle is as follows:

The “creatures” prepare $n$ strawberry strings, and the sum of their lengths $<= 10^6$. Now they can perform the following operations:

$1\ x\ l\ r$ means copying the substring $[l,r]$ of the strawberry string with index $x$, and inserting the copied string into the current set of strawberry strings. It is guaranteed that the length of string $x$ is $>=r$.

$2\ k$ means deleting the strawberry string that was inserted by the $k$-th operation. It is guaranteed that the $k$-th operation is an insertion, and the string inserted by the $k$-th operation is currently in the set.

The “creatures” believe that a harmonious flavor is delicious. After performing any operation, they want to know the deliciousness of all strawberry strings in the current set (i.e., $LCP$ - the longest common prefix). (If the set is empty, the deliciousness is $0$. If there is only one strawberry string in the set, the deliciousness is the length of that string.)

For convenience, we represent each type of strawberry as a lowercase English letter.

Many years later, Madeline comes to the Mirror Temple again, wanting to recall her climbing journey from long ago, but she no longer remembers how she solved that puzzle back then. Can you help her find the answer to the puzzle?

Input Format

The first line contains a positive integer $n$, indicating the number of strawberry strings.

The next $n$ lines each contain a string consisting of only lowercase letters, representing the original $n$ strawberry strings.

The next line contains a positive integer $q$, indicating the number of operations.

The next $q$ lines each contain one operation.

Output Format

Output $q$ lines. Each line should be the deliciousness ($LCP$ - the longest common prefix) of the strawberry strings in the set after the corresponding operation.

3
abccccd
abccddc
acbbcad
5
1 1 1 7
1 2 1 7
1 3 1 7
2 3
2 2

7
4
1
4
7

Hint

Sample explanation:

After the first operation, the set is $\{"abccccd"\}$, $LCP=7$.

After the second operation, the set is $\{"abccccd","abccddc"\}$, $LCP=4$.

After the third operation, the set is $\{"abccccd","abccddc","acbbcad"\}$, $LCP=1$.

The fourth operation deletes the string inserted by the third operation, so $LCP=4$.

The fifth operation deletes the string inserted by the second operation, so $LCP=7$.

Let $len$ be the sum of lengths of the $n$ strings. We always have $len \leq 10^6$.

Subtask $1$ ($10$ Pts): $n \leq 5, q = 10$.

Subtask $2$ ($30$ Pts): $n \leq 10^6, q = 10^6$, and it is guaranteed that each insertion is a prefix of a string.

Subtask $3$ ($10$ Pts): $n \leq 10^6, q = 10^5$, there are no type $2$ operations, and it is guaranteed that the queries are randomly generated.

Subtask $4$ ($50$ Pts): $n \leq 10^6, q = 10^6$.

Hint: You can determine the subtask number based on $q$.

Translated by ChatGPT 5