We are given three strings, $$$s$$$, $$$t$$$ and $$$p$$$. We will denote the length of a string by vertical bars, thus $$$|s|$$$ is the length of $$$s$$$ and so on. If we insert $$$t$$$ into $$$s$$$ at position $$$k$$$, where $$$0 \le k \le |s|$$$, the result is a new string consisting of the first $$$k$$$ characters of $$$s$$$, followed by the entirety of $$$t$$$, and finally followed by the remaining $$$|s| - k$$$ characters of $$$s$$$. We would like to select $$$k$$$ so that the resulting new string will contain the largest possible number of occurrences of $$$p$$$ as a substring.
Thus, for example, inserting $$$t = \texttt{aba}$$$ into $$$s = \texttt{ab}$$$ at position $$$k = 0$$$ results in the string $$$\texttt{abaab}$$$; at $$$k = 1$$$, in the string $$$\texttt{aabab}$$$; and at $$$k = 2$$$, in the string $$$\texttt{ababa}$$$. If we are interested in occurrences of $$$p = \texttt{aba}$$$, then the best position to insert $$$t$$$ into $$$s$$$ is $$$k = 2$$$, where we get two occurrences: $$$\texttt{ababa}$$$ and $$$\texttt{ababa}$$$ (as this example shows, occurrences of $$$p$$$ are allowed to overlap). If, on the other hand, we were interested in occurrences of $$$p = \texttt{aa}$$$, then the best choices of $$$k$$$ would be $$$k = 0$$$ and $$$k = 1$$$, which result in one occurrence of $$$p$$$, whereas $$$k = 2$$$ results in 0 occurrences of $$$p$$$.
The first line contains the string $$$s$$$, the second line the string $$$t$$$, and the third line the string $$$p$$$.
Input limits
Output one line containing the following four integers, separated by spaces:
ab aba aba
2 1 2 2
abaab aba ababa
1 3 1 5
eeoeo eoe eeo
2 3 1 4
The first of these three examples is the one discussed earlier in the problem statement.