文字列検索

文字列 T の中から文字列 P と一致する部分を探してください。P と一致する部分について、文字列 T の左端の位置 i (i = 0, 1, ..., Tの長さ -1) を順番にすべて報告してください。

入力

１行目に文字列 T、２行目に文字列 P が与えられる。

出力

各出現位置を１行に、順番に出力する。

制約

• 1 ≤ T の長さ ≤ 1000000
• 1 ≤ P の長さ ≤ 10000
• 文字列は、英小文字、英大文字、数字のみで構成されている。

入力例 1

aabaaa
aa

出力例 1

0
3
4

入力例 2

xyzz
yz

出力例 2

1

入力例 3

abc
xyz

出力例 3

出力なし。

---