分数: 400 点
问题陈述
Takahashi 在确定服务的用户名时遇到问题。 写一个代码来帮助他。
查找字符串 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',按此顺序。
- 让 S_1', S_2', \ldots,S_N' 是以下的排列 S_1, S_2, \ldots,S_N。 让 X 是以下的串联 S_1', (1 或多份
- 的长度 X 介于 3 和 16,包括在内。
- X 与以下任何一项都不相符 M 字符串 T_1,T_2,\ldots,T_M.
如果没有 X 满足所有条件,打印 -1 代替。
约束
- 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
- S_i \neq S_j if i \neq j.
- S_i 是由小写英文字母组成的字符串。
- 3 \leq |T_i| \leq 16
- T_i \neq T_j if i \neq j.
- T_i 是由小写英文字母和
_.
输入
输入由标准输入按以下格式给出:
N M S_1 S_2 \vdots S_N T_1 T_2 \vdots T_M
输出
打印字符串 X 满足所有条件。 如果没有 X 满足所有条件,打印 -1 代替。
如果有多个解决方案,请打印其中任何一个。
示例输入 1
1 1 chokudai chokudai
示例输出 1
-1
唯一满足第一个和第二个条件的字符串是 X= chokudai,但它与 T_1.
因此,没有 X 满足所有条件,所以 -1 。
示例输入 2
2 2 choku dai chokudai choku_dai
示例输出 2
dai_choku
字符串如 choku__dai (有两个 _之间 choku 和 dai) 也满足所有条件。
示例输入 3
2 2 chokudai atcoder chokudai_atcoder atcoder_chokudai
示例输出 3
-1
chokudai__atcoder 和 atcoder__chokudai (有两个 _之间 chokudai 和 atcoder) 的长度为 17,这违反了第二个条件。
示例输入 4
4 4 ab cd ef gh hoge fuga ____ _ab_cd_ef_gh_
示例输出 4
ab__ef___cd_gh
给定 T_i 可能包含无法通过第一个条件中描述的过程获得的字符串。