Migrated from Lutece 2210 qh与复读机III

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

qh今天想杀一批复读机。

qh把最近几天的聊天记录扒了出来，用一种神奇的编码方式将聊天记录转换成了由小写字母组成的字符串。

qh从记忆中挑选了一条经常被复读的语录，如orzqhqh，他想知道这条语录被哪些复读机复读了。

qh不想知道精确的复读位置，所以你只需要输出这条语录在聊天记录中的所有出现位置，而不用担心不同的出现位置相互重叠。如orzqhqhqh中出现了两次qhqh，位置分别为4和6。

检查聊天记录非常耗时，于是qh把这件事丢给了后缀复读机。

后缀复读机有一万个ddl要赶，没时间看聊天记录。

你能帮后缀复读机解决检查聊天记录的问题吗？

Input

第一行有一个仅由小写字母组成的字符串$S$，代表聊天记录。

第二行有一条仅由小写字母组成的语录$T$。

Output

输出$T$在$S$中的所有出现位置。

Samples

aaabcaabcaabaabcaabaabcaab
aabcaabaabcaa

6 13

Constraints

$1\leq |S|,|T| \leq 10^6$

Resources

2019 UESTC ACM Training for Search Algorithm and String