题目描述

Mushroom 最近看上了一个漂亮妹纸。他选择一种非常经典的手段来表达自己的心意——写情书。考虑到自己的表达能力，Mushroom 决定不手写情书。他从网上找到了两篇极佳的情书，打算选择其中共同的部分。另外 Mushroom 还有个一个情敌 Ertanis，此人也写了封情书给妹子。

Mushroom 不希望自己的情书中完整的出现了情敌的情书（这样抄袭的事情就暴露了）。

Mushroom 把两封情书分别用字符串 $s1$ 和 $s2$ 来表示，Ertanis 的情书用字符串 $s3$ 来表示，他要截取的部分用字符串 $w$ 表示。

需满足：

• $w$ 是 $s1$ 的子串
• $w$ 是 $s2$ 的子串
• $s3$ 不是 $w$ 的子串
• $w$ 的长度应尽可能大

所谓子串是指：在字符串中连续的一段。

输入格式

输入有三行，第一行为一个字符串 $s1$ 第二行为一个字符串 $s2$，第三行为一个字符串 $s3$。输入仅含小写字母，字符中间不含空格。

输出格式

输出仅有一行，为 $w$ 的最大可能长度，如 $w$ 不存在，则输出 0。

abcdef
abcf
bc

2

样例解释

$s1$ 和 $s2$ 的公共子串有 abc，ab，bc，a，b，c，f，其中 abc，bc 包含子串 bc 不合法，所以最长的合法子串为 ab。

数据规模与约定

对于 $100\%$ 的数据，$1 \le |s1|,|s2| \le 5 \times 10^4$，$1 \le |s3| \le 10^4$。