H. Insertions
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$.

Input

The first line contains the string $$$s$$$, the second line the string $$$t$$$, and the third line the string $$$p$$$.

Input limits

  • $$$1 \leq |s| \leq 10^5$$$
  • $$$1 \leq |t| \leq 10^5$$$
  • $$$1 \leq |p| \leq 10^5$$$
  • All the strings consist only of lowercase letters of the English alphabet.
Output

Output one line containing the following four integers, separated by spaces:

  1. The maximum number of occurrences of $$$p$$$ we can get after inserting $$$t$$$ into $$$s$$$ at position $$$k$$$, if we choose the position $$$k$$$ wisely.
  2. The number of different $$$k$$$'s (from the range $$$0, 1, \ldots, |s|$$$) where this maximum number of occurrences of $$$p$$$ is attained.
  3. The minimum value of $$$k$$$ where the maximum number of occurrences of $$$p$$$ is attained.
  4. The maximum value of $$$k$$$ where the maximum number of occurrences of $$$p$$$ is attained.
Examples
Input
ab
aba
aba
Output
2 1 2 2
Input
abaab
aba
ababa
Output
1 3 1 5
Input
eeoeo
eoe
eeo
Output
2 3 1 4
Note

The first of these three examples is the one discussed earlier in the problem statement.