AT_abc268_d [ABC268D] Unique Username

[problemUrl]: https://atcoder.jp/contests/abc268/tasks/abc268_d > 高橋君はあるサービスで使うユーザー名を決めるのに困っています。彼を助けるプログラムを書いてください。 以下の条件をすべて満たす文字列 $ 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 $ とする。 - $ 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 $ を $ 1 $ つ出力せよ。ただし、条件をすべて満たす文字列 $ 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 $ は英小文字と `_` のみからなる文字列 ### Sample Explanation 1 条件のうち $ 1 $ 番目と $ 2 $ 番目を満たす文字列は $ X= $ `chokudai` しかありませんが、これは $ T_1 $ と一致します。 このため、条件をすべて満たす文字列 $ X $ が存在せず、`-1` が正しい出力となります。 ### Sample Explanation 2 この他に、`choku\_\_dai` (`choku` と `dai` の間の `\_` が $ 2 $ つ) 等も条件をすべて満たします。 ### Sample Explanation 3 `chokudai\_\_atcoder` や `atcoder\_\_chokudai` (`chokudai` と `atcoder` の間の `\_` が $ 2 $ つ)は文字数が $ 17 $ なので $ 2 $ 番目の条件を満たしません。 ### Sample Explanation 4 $ 1 $ 番目の条件で記述されている操作で得られないような文字列が $ T_i $ として与えられる場合があります。