唯一用户名

题目描述

高桥君正在为某个服务的用户名而苦恼。请编写代码帮助他。

求一个满足以下所有条件的字符串 $X$：

$X$ 通过以下步骤得到：

设 $S_1', S_2', \ldots, S_N'$ 是 $S_1, S_2, \ldots, S_N$ 的一个排列。$X$ 为按顺序依次连接 $S_1'$、（$1$ 个以上的 _）、$S_2'$、（$1$ 个以上的 _）、$\ldots$、（$1$ 个以上的 _）和 $S_N'$ 得到的字符串。

$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$。如果不存在满足所有条件的 $X$，则输出 -1。

如果有多个解，输出任意一个即可。

样例

1 1
chokudai
chokudai

-1

满足第 1、2 个条件的唯一字符串是 $X =$ chokudai，但它与 $T_1$ 相同。 因此不存在满足所有条件的 $X$，应输出 -1。

2 2
choku
dai
chokudai
choku_dai

dai_choku

像 choku__dai（在 choku 和 dai 之间有两个 _）这样的字符串也满足所有条件。

2 2
chokudai
atcoder
chokudai_atcoder
atcoder_chokudai

-1

chokudai__atcoder 和 atcoder__chokudai（在 chokudai 和 atcoder 之间有两个 _）的长度为 $17$，违反了第 2 个条件。

4 4
ab
cd
ef
gh
hoge
fuga
____
_ab_cd_ef_gh_

ab__ef___cd_gh

给定的 $T_i$ 中可能包含无法通过第 1 个条件所述步骤得到的字符串。

数据范围

• $1 \le N \le 8$
• $0 \le M \le 10^5$
• $N$ 和 $M$ 是整数。
• $1 \le |S_i| \le 16$
• $N-1+\sum{|S_i|} \le 16$
• 当 $i \neq j$ 时，$S_i \neq S_j$。
• $S_i$ 是由小写英文字母组成的字符串。
• $3 \le |T_i| \le 16$
• 当 $i \neq j$ 时，$T_i \neq T_j$。
• $T_i$ 是由小写英文字母和 _ 组成的字符串。

提示

答案不唯一，输出任意合法解即可。