题目描述

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




例如： 




s=ABADABCEABABA， 




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




1 9 11 。

输入格式

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




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




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

输出格式

1 行，按题意输出  




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

样例

输入

ABADABCEABABA
ABA

输出

1 9 11

来源

KMP