题目描述

给定一个父字符串 $s$ 和子字符串 $p$ ，请按照从前向后的顺序，请求出 $p$ 在 $s$ 中所有出现的起始位置。

例如： $s = ABADABCEABABA$ ， $p = ABA$ ，则求解的结果是： $1$ $9$ $11$ 。

输入

第 $1$ 行读入一个仅包含大写字母的字符串 $s$ ；

第 $2$ 行读入一个仅包含大写字母的字符串 $p$ ；

$s$ 和 $p$ 均是长度不超过 $10^6$ 的字符串。

输出

输出 $1$ 行，按题意输出 $p$ 在 $s$ 中出现的位置，数字之间用空格隔开。

样例

ABADABCEABABA
ABA

1 9 11