Substring Query Maximization

You are given n template strings S₁, S₂, …, S_n composed of lowercase English letters, and q queries. There are two types of queries:

1. 1 T: A query string T (a string of lowercase letters) is given. Add this query string to the collection.
2. 2 p l r: For template string S_p, define
   $$num(p,l,r)=\text{ the number of query strings (from type 1 queries) in which }S_p[l,r]\text{ appears as a substring.}$$
   You are to compute $$\max_{1\le i\le l} \; num(p,i,r).$$

Note: The string indices are 1-indexed. For a query of type 2, you should consider all possible starting indices i from 1 to l and determine the maximum count among the substrings S_p[i,r].

inputFormat

The first line contains two integers n and q — the number of template strings and the total number of queries respectively.

Then follow n lines, each containing a template string S_i (composed of lowercase letters).

Then follow q lines, each containing a query in one of the following formats:

• 1 T — add the query string T to the collection.
• 2 p l r — for the template S_p, evaluate $$\max_{1\le i\le l}num(p,i,r)$$ as described above.

outputFormat

For each query of type 2, output a single integer — the maximum value of num(p,i,r) over all i from 1 to l, on a separate line.

sample

2 5
abc
bcd
1 abc
1 bc
2 1 1 2
1 abc
2 2 1 3

1
0