I. 宠物对战
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

最近 YahAHa 沉迷于一款宠物对战的游戏，这个游戏有两只宠物对战。YahAHa 经常用电脑模拟对战的过程，但最近程序出了问题，于是他碰到了一个问题，他想来问问聪明的你。

现在有两类字符串，$$$A$$$ 类和 $$$B$$$ 类，$$$A$$$ 类字符串有 $$$n$$$ 个，$$$B$$$ 类字符串有 $$$m$$$ 个，每个字符串仅由小写字母组成。用这两类字符串交替拼接可以形成一个新的字符串，形如 $$$abababab$$$……和 $$$bababababa$$$……，其中 $$$a$$$ 表示 $$$A$$$ 类中的某个字符串，$$$b$$$ 表示 $$$B$$$ 类中的某个字符串。注意，同一个字符串可以被重复利用。

现在他有一个字符串 $$$S$$$ ，他想问问你，$$$S$$$ 是否是由 $$$A、B$$$ 两类字符串交替拼接而成（即是否是上述的两种形式之一）。如果是，请输出 $$$S$$$ 最少由多少个字符串拼接而成；如果不是，请输出 -1 。

Input

第一行一个整数 $$$n(1\leq n\leq 10^5)$$$ 表示 $$$A$$$ 类字符串的个数。

接下来 $$$n$$$ 行，每行一个字符串 $$$a_i$$$ 表示 $$$A$$$ 类里的字符串。$$$∑ |a_i|\leq 5\times 10^5$$$

接下来一行一个整数 $$$m(1\leq m\leq 10^5)$$$ 表示 $$$B$$$ 类字符串的个数。

接下来 $$$m$$$ 行，每行一个字符串 $$$b_i$$$ 表示 $$$B$$$ 类里的字符串。$$$∑ |b_i|\leq 5\times 10^5$$$

接下来一行一个字符串 $$$S$$$ 表示 Stump 问你的字符串$$$(1\leq |s|\leq 5000)$$$ 。

Output

一行一个整数表示答案。

Examples
Input
1
ccpc
1
female
ccpcfemale
Output
2
Input
2
cc
pc
1
female
ccpcfemale
Output
-1
Input
2
cc
pc
1
female
ccfemalepc
Output
3
Input
2
cc
pc
1
female
femalecc
Output
2