KMP

Input

The first line contains the string $text$, and the second line contains the string $word$. The lengths of both strings are greater than $0$ and less than $50000$. The strings consist only of Latin letters.

Output

Print the starting indices of all occurrences of the string $word$ in the string $text$ in increasing order. As is customary in programming, indexing starts from $0$.

Examples