Cho xâu ~A~ và xâu ~B~ chỉ gồm các chữ cái thường. Xâu ~B~ được gọi là xuất hiện tại vị trí ~i~ của xâu ~A~ nếu: ~A[i]~ = ~B[1], A[i+1] = B[2], ..., A[i+length(B)-1] = B[length(B)]~.

Yêu cầu: Hãy tìm tất cả các vị trí mà ~B~ 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.

Ví dụ:

input

aaaaa
aa

output

1 2 3 4