配点 : 400 点
問題文
高桥君经常使用名为 Yafoo 的搜索引擎。
Yafoo 中 N 个网站已注册,i 第几个网站的注册名是 S_i 。 此外,字符串 T 作为搜索词进行搜索,在已注册的 N 个网站中,注册名的长度为 |T| 以上且以注册名开头 |T| 人物 T 的所有网站都会作为搜索结果获得。
现在,高桥君作为搜索结果 A_1,\ A_2,\ ...,\ A_K 我想要获取第 N 个网站。请判断是否存在能够正好得到这样的搜索结果的搜索词,如果存在,请在其中找到长度最短的那个。
制約
- 1 ≦ N ≦ 10^5
- 1 ≦ K ≦ N
- 1 ≦ A_i ≦ N
- 各 A_i 是不同的。
- 1 ≦ |S_i| ≦ 10^5
- |S_i| 的总和是 不超过 10^5 下面。
- S_i 由各个小写英文字母组成。
入力
输入是按以下格式从标准输入给出的。
N K A_1 A_2 ... A_K S_1 S_2 : S_N
出力
输出高桥君应作为搜索词的字符串中最短的一行。
但如果不存在这样的字符串,则改为 -1 。
入力例 1
3 2 1 2 abc ab a
出力例 1
ab
ab 这个字符串符合搜索词的条件。
入力例 2
3 2 1 2 abc ab abc
出力例 2
-1
入力例 3
3 3 1 2 3 abc ab abc
出力例 3
请注意,搜索词也可以是空字符串。