Description

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

例如：

s=ABADABCEABABA，

p=ABA，则求解的结果是：

1 9 11 。

Input Format

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

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

s 和 p 均是长度不超过 1e6的字符串。数据保证s中至少存在一个p

Output Format

1 行，按题意输出

p 在 s 中出现的位置，数字之间用空格隔开。

ABADABCEABABA
ABA

1 9 11

Source