{"raw_statement":[{"iden":"problem statement","content":"> Takahashi is having trouble with deciding a username for a service. Write a code to help him.\n\nFind a string $X$ that satisfies all of the following conditions:\n\n*   $X$ is obtained by the following procedure:\n    *   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.\n*   The length of $X$ is between $3$ and $16$, inclusive.\n*   $X$ does not coincide with any of $M$ strings $T_1,T_2,\\ldots,T_M$.\n\nIf there is no $X$ that satisfies all of the conditions, print `-1` instead."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 8$\n*   $0 \\leq M \\leq 10^5$\n*   $N$ and $M$ are integers.\n*   $1 \\leq |S_i| \\leq 16$\n*   $N-1+\\sum{|S_i|} \\leq 16$\n*   $S_i \\neq S_j$ if $i \\neq j$.\n*   $S_i$ is a string consisting of lowercase English letters.\n*   $3 \\leq |T_i| \\leq 16$\n*   $T_i \\neq T_j$ if $i \\neq j$.\n*   $T_i$ is a string consisting of lowercase English letters and `_`."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$S_1$\n$S_2$\n$\\vdots$\n$S_N$\n$T_1$\n$T_2$\n$\\vdots$\n$T_M$"},{"iden":"sample input 1","content":"1 1\nchokudai\nchokudai"},{"iden":"sample output 1","content":"\\-1\n\nThe only string that satisfies the first and second conditions is $X=$ `chokudai`, but it coincides with $T_1$.  \nThus, there is no $X$ that satisfies all of the conditions, so `-1` should be printed."},{"iden":"sample input 2","content":"2 2\nchoku\ndai\nchokudai\nchoku_dai"},{"iden":"sample output 2","content":"dai_choku\n\nStrings like `choku__dai` (which has two `_`'s between `choku` and `dai`) also satisfy all of the conditions."},{"iden":"sample input 3","content":"2 2\nchokudai\natcoder\nchokudai_atcoder\natcoder_chokudai"},{"iden":"sample output 3","content":"\\-1\n\n`chokudai__atcoder` and `atcoder__chokudai` (which have two `_`'s between `chokudai` and `atcoder`) have a length of $17$, which violates the second condition."},{"iden":"sample input 4","content":"4 4\nab\ncd\nef\ngh\nhoge\nfuga\n____\n_ab_cd_ef_gh_"},{"iden":"sample output 4","content":"ab__ef___cd_gh\n\nThe given $T_i$ may contain a string that cannot be obtained by the procedure described in the first condition."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}