Mystical Mirror Temple and Strawberry Strings

In the Mystical Mirror Temple, a magical temple where one can glimpse the truth of their soul, Theo is trapped in a mirror. When Madeline tries to rescue him, the temple's mysterious creatures challenge her with a puzzle:

You are given n strawberry strings (each strawberry represented by a lowercase English letter) with the total length of all strings at most 10⁶. The creatures allow you to perform the following operations:

• 1 x l r: Copy the substring from position l to r (inclusive, 1-indexed) of the strawberry string with identifier x and insert it into the collection. It is guaranteed that the strawberry string with identifier x has length at least r.

• 2 k: Delete the strawberry string that was inserted by the k-th insertion operation. It is guaranteed that the k-th operation was an insertion and that the resulting string is still in the collection.

After each operation, the creatures want to know the deliciousness of the current collection, which is defined as the length of the longest common prefix (LCP) among all strawberry strings in the collection. If the collection is empty, the deliciousness is 0. If the collection contains only one string, the deliciousness is the length of that string.

Help Madeline remember how she solved this puzzle so many years ago.

inputFormat

The input begins with an integer n, the number of initial strawberry strings. Each of the next n lines contains a non-empty string consisting of lowercase English letters. Then an integer q is given, representing the number of operations. Each of the following q lines contains an operation in one of the following forms:

• 1 x l r – Copy the substring from position l to r from the strawberry string with identifier x and insert it into the collection.
• 2 k – Delete the strawberry string inserted by the k-th insertion operation.

After each operation, you should output a single integer: the deliciousness of the collection, as explained above.

outputFormat

For each operation, output a single integer — the deliciousness of the collection after that operation.

sample

2
abc
abx
3
1 1 2 3
1 2 1 2
2 1

0
0
2