C - 検索
解説
/
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 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
検索ワードは空文字列でも良いことに注意してください。