题目描述

小明在研究文本编辑器的查找功能。他想知道，给定一个文本串 $s_1$ 和一个模式串 $s_2$，$s_2$ 在 $s_1$ 中所有出现的位置（即 $s_1$ 的某个子串与 $s_2$ 完全匹配时，该子串的起始位置）。

同时，小明还需要计算 $s_2$ 的前缀函数（即 KMP 的 $\pi$ 数组）。对于 $s_2$ 的每个前缀 $s_2[0..i]$（$0 \le i \lt |s_2|$），前缀函数的值定义为该前缀的最长真 border 的长度。这里的 border 是指既是该前缀的前缀、又是该前缀的后缀，且不等于该前缀本身的子串。

输入格式

第一行为字符串 $s_1$。

第二行为字符串 $s_2$。

输出格式

首先输出若干行，每行一个整数，按从小到大的顺序输出 $s_2$ 在 $s_1$ 中所有出现的位置（1-indexed）。

最后一行输出 $|s_2|$ 个整数，第 $i$ 个整数表示 $s_2$ 长度为 $i$ 的前缀的最长 border 长度。相邻整数之间用一个空格分隔。

样例

ABABABC
ABA

1
3
0 0 1

提示

数据规模与约定

对于全部测试点，保证 $1 \le |s_1|,|s_2| \le 10^6$，$s_1, s_2$ 中仅包含大写英文字母。