Persistent String Set Queries

Given (S_0 = \varnothing), maintain a persistent data structure that supports the following operations:

1. Operation 1: 1 hoc s. Let (S_i = S_{hoc} \cup {s}), where (s) is a non-empty string and it is guaranteed that (s \notin S_{hoc}) before this operation.
   
   
2. Operation 2: 2 hoc s. Let (S_i = S_{hoc}) and query the sum of the occurrences of each string in (S_i) in the given string (s). The occurrences are counted in a non-overlapping manner.
   
   Note: The operations are persistent. The index (i) of each operation is from 1 to (n), and the base set (S_0) is empty.

inputFormat

The first line contains an integer (n) representing the number of operations. Each of the following (n) lines describes an operation in one of the two formats:

• For operation 1: 1 hoc s
• For operation 2: 2 hoc s

Here, (hoc) is an integer indicating the index of the source set from which the new set is derived, and (s) is a non-empty string.

outputFormat

For each operation of type 2, output a single line with the sum of the number of occurrences (non-overlapping) of every string in (S_{hoc}) in the given string (s).

sample

5
1 0 a
1 1 b
2 2 abababa
1 2 ab
2 3 abababa

7
10