Aho$$Corasick algorithm

Cost: $12|$ Solved: $2$

Memory limit: $512$ Mb

Time limit: $1000$ ms

Input file: stdin

Output file: stdout

$**$ Use only C$++**$

Task:

You have to write the implementation of Aho$-$Corasick algorithm that finds a certain substring in a string.

Input:

The first line contains a string $s.$

The second line contains a natural $m-$ the number of substrings.

Each of the next $m$ lines contains a substring that is needed to be found in the string $s.$

Output:

For each substring $($one per line$),$ output all the indexes of a subtring's appearance in the string $s$ in ascending order.

Example: