E. 弱者都是群居者
time limit per test
1 с
memory limit per test
1024 megabytes
input
standard input
output
standard output

我们给出一些弱的字符串 $$$T_i$$$ ，而如果 $$$T_i$$$ 作为一个字符串 $$$T'$$$ 的子串出现，那么 $$$T'$$$ 也是弱的。对于一个字符串 $$$S$$$，我们希望在其中任意截取的子串都是弱的。我们限制所截取子串的长度至少为 $$$k$$$，如果要满足上述限制，则这个 $$$k$$$ 的最小值是多少？

换句话说，你要找到一个最小长度 $$$k$$$ ，使得从文本串 $$$S$$$ 中截取出任意长度大于等于 $$$k$$$ 的子串，都至少有一个模式串是它的子串。如果不能找到这样一个长度，则输出 $$$-1$$$。

Input

第一行一个正整数 $$$n (1 \leq n \leq 2 \times 10^5)$$$，表示模式串个数。

接下来 $$$n$$$ 行，为分别为一个模式串 $$$T_i (1 \leq |T_i| \leq 5 \times 10^4, \Sigma |T_i| \leq 5 \times 10^5)$$$

最后一行为一个文本串 $$$S (1 \leq |S| \leq 4 \times 10^6)$$$

保证所有输入的字符串都是由小写字母组成。

Output

输出最小的子串长度 $$$k$$$。如果不存在，则输出 $$$-1$$$。

Example
Input
3
ab
bcd
bc
abcd
Output
3