/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
高橋君はあるサービスで使うユーザー名を決めるのに困っています。彼を助けるプログラムを書いてください。
以下の条件をすべて満たす文字列 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 とする。
- N 個の文字列 S_1,S_2,\ldots,S_N を好きな順番で並べたものを S_1', S_2', \ldots,S_N' とする。そして、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
- 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 は英小文字と
_のみからなる文字列
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 S_2 \vdots S_N T_1 T_2 \vdots T_M
出力
条件をすべて満たす文字列 X を 1 つ出力せよ。ただし、条件をすべて満たす文字列 X が存在しない場合は代わりに -1 を出力せよ。
答えが複数存在する場合、どれを出力しても良い。
入力例 1
1 1 chokudai chokudai
出力例 1
-1
条件のうち 1 番目と 2 番目を満たす文字列は X= chokudai しかありませんが、これは T_1 と一致します。
このため、条件をすべて満たす文字列 X が存在せず、-1 が正しい出力となります。
入力例 2
2 2 choku dai chokudai choku_dai
出力例 2
dai_choku
この他に、choku__dai (choku と dai の間の _ が 2 つ) 等も条件をすべて満たします。
入力例 3
2 2 chokudai atcoder chokudai_atcoder atcoder_chokudai
出力例 3
-1
chokudai__atcoder や atcoder__chokudai (chokudai と atcoder の間の _ が 2 つ)は文字数が 17 なので 2 番目の条件を満たしません。
入力例 4
4 4 ab cd ef gh hoge fuga ____ _ab_cd_ef_gh_
出力例 4
ab__ef___cd_gh
1 番目の条件で記述されている操作で得られないような文字列が T_i として与えられる場合があります。
Score : 400 points
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.
- 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
- 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.