题目描述

高橋君はあるサービスで使うユーザー名を決めるのに困っています。彼を助けるプログラムを書いてください。

以下の条件をすべて満たす文字列 $X$ を $1$ つ求めてください。

• $X$ は次の手順で得られる文字列である。
  • $N$ 個の文字列 $S_1,S_2,\ldots,S_N$ を好きな順番で並べたものを $S_1',\ S_2',\ \ldots,S_N'$ とする。そして、$S_1'$、( $1$ 個以上の _ )、$S_2'$、( $1$ 個以上の _ )、$\ldots$、( $1$ 個以上の _ )、$S_N'$ をこの順番で連結したものを $X$ とする。
• $X$ の文字数は $3$ 以上 $16$ 以下である。
• $X$ は $M$ 個の文字列 $T_1,T_2,\ldots,T_M$ のいずれとも一致しない。

ただし、条件をすべて満たす文字列 $X$ が存在しない場合は代わりに -1 と出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $S_1$ $S_2$ $\vdots$ $S_N$ $T_1$ $T_2$ $\vdots$ $T_M$

输出格式

条件をすべて満たす文字列 $X$ を $1$ つ出力せよ。ただし、条件をすべて満たす文字列 $X$ が存在しない場合は代わりに -1 を出力せよ。
答えが複数存在する場合、どれを出力しても良い。

题目大意

高桥君有取名选择困难症，于是他找到你，希望帮他取一个用户名。

具体取名规则是：把给定的 $N$ 个字符串 $S_1，S_2,\ldots,S_N$ 以任意顺序排列，并在每两个字符串中间加 $\ge1$ 个下划线，要求不能与后面给定的 $M$ 个字符串 $T_1，T_2,\ldots,T_M$ 中的任意一个相同。

其中，你给出的字符串的长度 $X$ 应该满足 $3\le X \le 16$ 。如果无法满足条件，输出 $-1$。

输入格式

第一行两个整数，分别为 $N$ 和 $M$ ；

后 $N$ 行每行一个字符串 $S_i$ ；

后 $M$ 行每行一个字符串 $T_i$ 。

输出格式

一个满足题意的字符串 $X$ 。如果没有满足的，输出一个数 $-1$ 。

1 1
chokudai
chokudai

-1

2 2
choku
dai
chokudai
choku_dai

dai_choku

2 2
chokudai
atcoder
chokudai_atcoder
atcoder_chokudai

-1

4 4
ab
cd
ef
gh
hoge
fuga
____
_ab_cd_ef_gh_

ab__ef___cd_gh

提示

制約

• $1\ \leq\ N\ \leq\ 8$
• $0\ \leq\ M\ \leq\ 10^5$
• $N,M$ は整数
• $1\ \leq\ |S_i|\ \leq\ 16$
• $N-1+\sum{|S_i|}\ \leq\ 16$
• $i\ \neq\ j$ ならば $S_i\ \neq\ S_j$
• $S_i$ は英小文字のみからなる文字列
• $3\ \leq\ |T_i|\ \leq\ 16$
• $i\ \neq\ j$ ならば $T_i\ \neq\ T_j$
• $T_i$ は英小文字と _ のみからなる文字列

Sample Explanation 1

条件のうち $1$ 番目と $2$ 番目を満たす文字列は $X=$ chokudai しかありませんが、これは $T_1$ と一致します。 このため、条件をすべて満たす文字列 $X$ が存在せず、-1 が正しい出力となります。

Sample Explanation 2

この他に、choku\_\_dai (choku と dai の間の \_ が $2$ つ) 等も条件をすべて満たします。

Sample Explanation 3

chokudai\_\_atcoder や atcoder\_\_chokudai (chokudai と atcoder の間の \_ が $2$ つ)は文字数が $17$ なので $2$ 番目の条件を満たしません。

Sample Explanation 4

$1$ 番目の条件で記述されている操作で得られないような文字列が $T_i$ として与えられる場合があります。