Knuth$-$Morris$-$Pratt algorithm

Cost: $8|$ Solved: $5$

Memory limit: $256Mb$

Time limit: $1000$ ms

Input file: stdin

Output file: stdout

Task:

You have to write the implementation of Knuth$-$Morris$-$Pratt 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.

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