题目描述

给出两个只含大写英文字母的字符串 $s_1,s_2$，请求出：

1. $s_2$ 在 $s_1$ 中所有出现位置的起始下标（下标从 $1$ 开始），按从小到大的顺序每行输出一个；
2. $s_2$ 的前缀函数（border 数组）$nxt_1,nxt_2,\dots,nxt_{|s_2|}$，即每个前缀的最长 border 长度。

输入格式

共两行，第一行字符串 $s_1$。

第二行字符串 $s_2$。

输出格式

先输出若干行，每行一个整数，表示 $s_2$ 在 $s_1$ 中出现位置的起始下标。

最后一行输出 $|s_2|$ 个整数 $nxt_1,nxt_2,\dots,nxt_{|s_2|}$，相邻两个数之间用一个空格隔开。

输入输出样例 #1

输入 #1

ABABABC
ABA

输出 #1

1
3
0 0 1

说明

数据范围

• 对于 $100\%$ 的数据，$1\le |s_2|\le |s_1|\le 5\times 10^5$。