给定三个字符串 $s$、$t$ 和 $p$。我们用竖线表示字符串的长度，例如 $|s|$ 表示 $s$ 的长度，以此类推。如果我们将 $t$ 插入到 $s$ 的位置 $k$（其中 $0 \le k \le |s|$），得到的新字符串由 $s$ 的前 $k$ 个字符、完整的 $t$ 以及 $s$ 剩余的 $|s| - k$ 个字符组成。我们希望选择一个 $k$，使得生成的新字符串中包含尽可能多的 $p$ 作为子串。

例如，将 $t = \text{aba}$ 插入到 $s = \text{ab}$ 的位置 $k = 0$ 得到字符串 $\text{abaab}$；在 $k = 1$ 时得到 $\text{aabab}$；在 $k = 2$ 时得到 $\text{ababa}$。如果我们关注 $p = \text{aba}$ 的出现次数，那么插入 $t$ 的最佳位置是 $k = 2$，此时我们得到两次出现：$\text{ababa}$ 和 $\text{ababa}$（如本例所示，允许 $p$ 的出现重叠）。另一方面，如果我们关注 $p = \text{aa}$ 的出现次数，那么最佳的 $k$ 选择是 $k = 0$ 和 $k = 1$，它们都会产生一次 $p$ 的出现，而 $k = 2$ 则产生 0 次 $p$ 的出现。

输入格式

第一行包含字符串 $s$，第二行包含字符串 $t$，第三行包含字符串 $p$。

数据范围

• $1 \le |s| \le 10^5$
• $1 \le |t| \le 10^5$
• $1 \le |p| \le 10^5$
• 所有字符串仅由小写英文字母组成。

输出格式

输出一行，包含四个由空格分隔的整数：

1. 如果我们明智地选择位置 $k$，将 $t$ 插入到 $s$ 中后，我们能得到的 $p$ 的最大出现次数。
2. 在范围 $0, 1, \dots, |s|$ 中，达到此最大出现次数的不同 $k$ 的个数。
3. 达到此最大出现次数的 $k$ 的最小值。
4. 达到此最大出现次数的 $k$ 的最大值。

样例

样例输入 1

ab
aba
aba

样例输出 1

2 1 2 2

样例输入 2

abaab
aba
ababa

样例输出 2

1 3 1 5

样例输入 3

eeoeo
eoe
eeo

样例输出 3

2 3 1 4

说明

第一个样例即为题目描述中讨论的例子。