Richelieu's Parades

Time limit2sMemory limit1024 MB

Summary

For each j, delete one length-j substring from t and find the most rows s_i whose prefix is the remaining string. Print the maximum for every j.

Level: Hard8 of 10
Topics: String matching, Trie, String
Solved: No attempts yet

Problem

Cardinal Richelieu decided to line up his guards today. The parade ground has $n$ rows. Each guard in a row wears a uniform of some color. There are 26 uniform colors, and each color is denoted by its own letter of the Latin alphabet.

Each row is given by a string $s_i$ . The start of the string is the front of the row, and the end of the string is the back of the row.

Several demonstration parades are planned. Richelieu has a string $t$ that he uses to build each parade. There will be $k$ parades in total, held as follows. For the $j$ -th parade, Richelieu deletes one substring of length $j$ from $t$ and calls the remaining string $t_j$ . Then he selects every row whose prefix equals $t_j$ , and those rows take part in the $j$ -th parade.

Input

The first line contains a string $t$ ( $1 \le |t| \le 10^5$ ) made of lowercase Latin letters.

The next line contains two positive integers $n$ and $k$ ( $1 \le n \le 10^5$ , $1 \le k < |t|$ ), where $n$ is the number of rows and $k$ is the number of parades.

Each of the following $n$ lines contains a row string $s_i$ . It is non-empty and made of lowercase Latin letters.

The total length of all $s_i$ does not exceed $10^5$ .

Output

Print $k$ integers on a single line. The $j$ -th number is the maximum number of rows that can take part in the $j$ -th parade.

Examples2

Example 1
Input
```
abcdef
3 3
abcefx
abcdfab
abcdf
```
Expected output
```
2 2 3
```
Example 2
Input
```
abcab
3 4
aaba
aabz
ad
```
Expected output
```
0 2 0 3
```