题目描述

给定一个字符串 $S$，以及一个模式串 $P$，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 $P$ 在字符串 $S$ 中多次作为子串出现。

求出模式串 $P$ 在字符串 $S$ 中所有出现的位置的起始下标。

输入格式

共两行，输入字符串 $P$ 和 $S$。

输出格式

共一行，输出所有出现位置的起始下标，整数之间用空格隔开。

数据范围

$1 \le N \le 10^5$ $1 \le M \le 10^6$

输入样例：

aba
ababa

输出样例：

1 3