Good Triplets Segmentation

Given n strings (S_1, S_2, \ldots, S_n) and a string (T), define a non‐empty string (R) to be a prefix of some (S_i) if there exists an integer (p) with (1 \le p \le |S_i|) such that (R = S_{i[1,p]}). Let the set of all good (non‐empty) strings be all prefixes of any (S_i). Additionally, the empty string is also considered good.

For any sequence of strings (R_1,R_2,\dots,R_k), denote by (R_1+R_2+\dots+R_k) their concatenation. A triplet ((l,r,k)) with integers (1\le l\le r\le |T|) and (1\le k\le K) is called a good triplet if there exist (k) good strings (R_1,R_2,\dots,R_k) (each being either empty or a prefix of some (S_i)) such that [ R_1+R_2+\dots+R_k = T_{[l,r]} ]

Note: For any valid segmentation of (T_{[l,r]}) into a sequence of non-empty substrings each belonging to the set of prefixes of some (S_i), one can always insert additional empty good strings into the sequence so as to obtain a sequence of exactly (k) strings as long as (k) is at least the minimal number of non-empty words needed.

Your task is to:

1. Count the total number of good triplets ((l,r,k)).
2. For each index (i) (where (1 \le i \le |T|)), count the number of good triplets ((l,r,k)) satisfying (l \le i \le r).

If you can only compute one of the two answers, you may receive partial score.

Input Format

The input begins with two integers (n) and (K). The next (n) lines each contain a string (S_i). The last line contains the string (T).

Output Format

Output two lines. The first line contains a single integer representing the total number of good triplets. The second line contains (|T|) integers, where the (i)th integer is the number of good triplets ((l,r,k)) with (l \le i \le r).

inputFormat

The first line contains two integers (n) and (K) separated by a space. The next (n) lines each contain a string (S_i). The final line contains the string (T).

outputFormat

The output consists of two lines. The first line is a single integer representing the total number of good triplets. The second line contains (|T|) space-separated integers where the (i)th integer is the count of good triplets ((l,r,k)) such that (l \leq i \leq r).

sample

2 3
a
ab
ab

6
6 3