List every position where pattern t occurs in text s. Occurrences may overlap and positions are one-based.

Input

The first line contains lowercase string s and the second contains lowercase string t (1 ≤ |t| ≤ |s| ≤ 1000000).

Output

Print all starting positions in increasing order, separated by spaces. Print -1 if there is no occurrence.

Examples

Input #1

abababa
ba

Output #1

2 4 6

Input #2

aaaaa
aa

Output #2

1 2 3 4