KMP

Find all occurrences of the string word in the string text.

Input

The first line contains the string text, the second line contains the string word. The length of each string is greater than 0 and less than 50000, the strings contain only latin letters.

Output

Print the position numbers from which the string word starts in a string text in ascending order. As is usually in programming, the string positions start from zero.

Examples