Xâu con

Đề bài: Cho xâu và xâu chỉ gồm các chữ cái thường. Xâu được gọi là xuất hiện tại vị trí của xâu A nếu: Ai=B1, Ai+1 =B2,…, Ai+length(B)-1 = Blength(B). Hãy tìm tất cả các vị trí mà xuất hiện trong A.

Input

·       Dòng 1: xâu A.

·       Dòng 2: xâu B.

Độ dài A, B không quá 1000000.

Output

·       Ghi ra các vị trí tìm được trên 1 dòng (thứ tự tăng dần). Nếu B không xuất hiện trong A thì bỏ trắng.

Nếu không tìm thấy thì in ra -1.

Ví dụ 1:

Input:

aaaaa

aa

Output:

1 2 3 4 

Ví dụ 2

Input:

abcdefg

xyz

Output:

-1