F. Interesting String Problem
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Since you are a good friend of Jaber and Eyad, they are asking for your help to solve this problem.

You are given a graph consisting of $$$n$$$ nodes, which initially has no edges. For each node $$$i$$$, there's a string $$$s_i$$$ of lowercase Latin letters written on it.

You have to process $$$q$$$ queries of two types:

  • 1 u v : it means add an edge between node $$$u$$$ and node $$$v$$$.
  • 2 u t : it means for node $$$u$$$ and string $$$t$$$, output the sum of $$$cnt_v$$$ over all nodes $$$v$$$ which belong to the same component as $$$u$$$,where $$$cnt_v$$$ is the number of times $$$s_v$$$ occurs in $$$t$$$ as a substring.
Input

The first line contains one integer number $$$n$$$ ($$$1 \le n \le 2 * 10^5$$$), the number of nodes in the given graph.

The following $$$n$$$ lines, the $$$i_{th}$$$ of them has the string $$$a_i$$$, the string written on the $$$i_{th}$$$ node.

The following line has one integer number $$$q$$$ ($$$1 \le q \le 2 * 10^5$$$), which is the number of queries.

The following $$$q$$$ lines have the queries in the following form:

  • 1 u v : for a query of the first type.
  • 2 u t : for a query of the second type.

It is guaranteed that the sum of lengths of $$$s_v$$$ doesn't exceed $$$5 * 10^5$$$, and sum of lengths of the query strings doesn't exceed $$$5 * 10^5$$$.

Output

For each query of the second type, print in a single line the answer to the query.

Example
Input
4
a
ab
ba
ca
7
2 2 abab
1 2 3
2 2 abab
1 1 3
2 2 acac
1 3 4
2 2 acac
Output
2
3
2
3