Ngoài sở thích tìm hiểu về dãy số thì xâu cũng là chủ đề mà Minh và Nam yêu thích. Một hôm, hai bạn muốn tìm hiểu xem tất cả vị trí xuất hiện của xâu này trong xâu kia.
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 kí tự.

Output

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

Example

ccccccc
ccc

1 2 3 4 5