「みんなのプロコン」

C - 検索


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 400

問題文

高橋君は Yafoo という検索エンジンをよく利用しています。

Yafoo には N 個のサイトが登録されており、i 個目のサイトの登録名は S_i です。 また、文字列 T を検索ワードとして検索を行うと、登録されている N 個のサイトのうち、 登録名の長さが |T| 以上でかつ登録名の先頭 |T| 文字が T に一致するようなサイト全てが検索結果として得られます。

今、高橋君は検索結果として A_1,\ A_2,\ ...,\ A_K 番目のサイトが得られるようにしたいです。 そのような検索結果がちょうど得られるような検索ワードが存在するかどうかを判定し、存在する場合はその中で長さが最小のものを求めてください。

制約

  • 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



検索ワードは空文字列でも良いことに注意してください。


Submit提出する