String Containment Queries

Alice has n strings \(S_1, S_2, \ldots, S_n\). Bob starts with an empty set \(T\) of strings. Then, there are q operations. Each operation is one of the following two types:

• 1 P: Bob adds the string \(P\) to his set \(T\).
• 2 x: Alice asks Bob how many strings in his set \(T\) contain the string \(S_x\) as a substring. (A string \(A\) is said to contain \(B\) if \(B\) is a contiguous subsequence of \(A\).)

For each query operation, print the corresponding count on a new line.

inputFormat

The first line contains two integers \(n\) and \(q\) separated by a space.

The next \(n\) lines each contain a non-empty string. The \(i\)th string is \(S_i\).

The following \(q\) lines describe an operation in one of the two formats:

• 1 P for adding a string \(P\) to set \(T\).
• 2 x for querying how many strings in \(T\) contain \(S_x\) as a substring.

outputFormat

For each operation of type 2, print one integer on a separate line, which is the number of strings in \(T\) that contain the corresponding \(S_x\) as a substring.

sample

2 5
a
ab
1 abcd
1 hello
2 1
2 2
2 1

1
1
1