给出两个字符串text和pattern，其中pattern为text的子串，求出pattern在text中所有出现的位置。

为了减少骗分的情况，接下来还要输出子串的前缀数组next。

输入格式:

第一行为一个字符串，即为text。

第二行为一个字符串，即为pattern。

输出格式:

若干行，每行包含一个整数，表示pattern在text中出现的位置。

接下来1行，包括length(pattern)个整数，表示前缀数组next[i]的值，数据间以一个空格分隔，行尾无多余空格。

输入样例:
ABABABC
ABA

输出样例:
1
3
0 0 1