{"problem":{"name":"Unique Username","description":{"content":"> 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","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc268_d"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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 `_`.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc268_d","tags":[],"sample_group":[["1 1\nchokudai\nchokudai","\\-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."],["2 2\nchoku\ndai\nchokudai\nchoku_dai","dai_choku\n\nStrings like `choku__dai` (which has two `_`'s between `choku` and `dai`) also satisfy all of the conditions."],["2 2\nchokudai\natcoder\nchokudai_atcoder\natcoder_chokudai","\\-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."],["4 4\nab\ncd\nef\ngh\nhoge\nfuga\n____\n_ab_cd_ef_gh_","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."]],"created_at":"2026-03-03 11:01:14"}}