← 返回题目列表

AtCoder · yahoo_procon2017_qual_c

C. 検索

中文机器翻译题面 查看原题

配点 : 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


请注意,搜索词也可以是空字符串。