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 )}~.

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.

Sample Input

aaaaa
aa

Sample Output

1 2 3 4