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)]\). (\(length(B)\) là độ dài của xâu \(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.

Example

aaaaa
aa

1 2 3 4

Nguồn: vn.spoj.com