← 返回题目列表

AtCoder · abc268_d

G. 唯一用户名

中文机器翻译题面 查看原题

分数: 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',按此顺序。
  • 的长度 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 可能包含无法通过第一个条件中描述的过程获得的字符串。