题目描述

给定一个文本串 $\mathtt{T}$ 和一个模式串 $\mathtt{P}$，计算文本串 $\mathtt{T}$ 中所有能够匹配到模式串 $\mathtt{P}$ 的位置。

输入格式

第一行，文本串 $\mathtt{T}$；

第二行，模式串 $\mathtt{P}$。

输出格式

如果 文本串 $\mathtt{T}$ 中存在模式串 $\mathtt{P}$，输出所有匹配上的位置，要求输出一行，按照下标从小到大输出，相邻下标之间以一个空格分隔。

如果不存在任何匹配到的位置，输出 $-1$。

注：这里所说的匹配上的位置指的是所有满足如下条件的下标 $p$：

$T_p$ 开始的长度为 $\mathtt{|P|}$ 的子串恰好等于模式串 $\mathtt{P}$（下标从 $1$ 开始，$\mathtt{|P|}$ 指的是模式串 $\mathtt{P}$ 的长度）。

样例

anjigaojizhongxue
ji

3 8

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$\mathtt{|T|} \le 100, \mathtt{|P|} \le 10$
• 对于 $60\%$ 的数据，$\mathtt{|T|} \le 10000, \mathtt{|P|} \le 1000$
• 对于 $100\%$ 的数据，$1 \le \mathtt{|T|} \le 10^6, 1 \le \mathtt{|P|} \le 10^6$，字符串均由小写英文字母构成