Score : $400$ points

问题描述

高桥在为一个服务选择用户名时遇到了困难。编写一段代码来帮助他。

找出满足以下所有条件的字符串 $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。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Takahashi is having trouble with deciding a username for a service. Write a code to help him.

Find a string $X$ that satisfies all of the following conditions:

• $X$ is obtained by the following procedure:
  • Let $S_1', S_2', \ldots,S_N'$ be a permutation of $S_1, S_2, \ldots,S_N$. Let $X$ be the concatenation of $S_1'$, ($1$ or more copies of _), $S_2'$, ($1$ or more copies of _), $\ldots$, ($1$ or more copies of _), and $S_N'$, in this order.
• The length of $X$ is between $3$ and $16$, inclusive.
• $X$ does not coincide with any of $M$ strings $T_1,T_2,\ldots,T_M$.

If there is no $X$ that satisfies all of the conditions, print -1 instead.

Constraints

• $1 \leq N \leq 8$
• $0 \leq M \leq 10^5$
• $N$ and $M$ are integers.
• $1 \leq |S_i| \leq 16$
• $N-1+\sum{|S_i|} \leq 16$
• $S_i \neq S_j$ if $i \neq j$.
• $S_i$ is a string consisting of lowercase English letters.
• $3 \leq |T_i| \leq 16$
• $T_i \neq T_j$ if $i \neq j$.
• $T_i$ is a string consisting of lowercase English letters and _.

Input

Input is given from Standard Input in the following format:

$N$ $M$

$S_1$

$S_2$

$\vdots$

$S_N$

$T_1$

$T_2$

$\vdots$

$T_M$

Output

Print a string $X$ that satisfies all of the conditions. If there is no $X$ that satisfies all of the conditions, print -1 instead.
If there are multiple solutions, print any of them.

Sample Input 1

1 1
chokudai
chokudai

Sample Output 1

-1

The only string that satisfies the first and second conditions is $X=$ chokudai, but it coincides with $T_1$.
Thus, there is no $X$ that satisfies all of the conditions, so -1 should be printed.

Sample Input 2

2 2
choku
dai
chokudai
choku_dai

Sample Output 2

dai_choku

Strings like choku__dai (which has two _'s between choku and dai) also satisfy all of the conditions.

Sample Input 3

2 2
chokudai
atcoder
chokudai_atcoder
atcoder_chokudai

Sample Output 3

-1

chokudai__atcoder and atcoder__chokudai (which have two _'s between chokudai and atcoder) have a length of $17$, which violates the second condition.

Sample Input 4

4 4
ab
cd
ef
gh
hoge
fuga
____
_ab_cd_ef_gh_

Sample Output 4

ab__ef___cd_gh

The given $T_i$ may contain a string that cannot be obtained by the procedure described in the first condition.

update @ 2024/3/10 11:18:23