String Occurrence and Border Computation

Given two strings \(s_1\) and \(s_2\), we say that \(s_2\) appears in \(s_1\) at position \(l\) if there exists an interval \([l, r]\) such that \(s_1[l,r] = s_2\). Your task is to find all the starting positions \(l\) where \(s_2\) appears in \(s_1\).

In addition, a border of a string \(s\) is defined as a non-trivial (i.e. not equal to \(s\) itself) substring \(t\) that is both a prefix and a suffix of \(s\). For the string \(s_2\), you are required to compute, for every prefix \(s'\) of \(s_2\), the length of its longest border.

Formally, if we denote by \(\pi(i)\) the length of the longest border of the prefix \(s_2[1\ldots i]\) (using 1-indexed positions), then your program should output these values for all \(i = 1, 2, \ldots, |s_2|\>.

inputFormat

The input consists of two lines:

1. The first line contains the string \(s_1\).
2. The second line contains the string \(s_2\).

outputFormat

The output should consist of two lines:

1. The first line contains the starting positions (1-indexed) where \(s_2\) appears in \(s_1\), separated by spaces. If there are no occurrences, output an empty line.
2. The second line contains \(|s_2|\) numbers, where the \(i\)-th number is the length of the longest border for the prefix \(s_2[1\ldots i]\), separated by spaces.

sample

abcabcdabc
abc

1 4 8
0 0 0