{"problem":{"name":"Prefix-free Game","description":{"content":"For strings $s$ and $t$, we will say that $s$ and $t$ are _prefix-free_ when neither is a prefix of the other. Let $L$ be a positive integer. A set of strings $S$ is a _good string set_ when the follo","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc087_c"},"statements":[{"statement_type":"Markdown","content":"For strings $s$ and $t$, we will say that $s$ and $t$ are _prefix-free_ when neither is a prefix of the other.\nLet $L$ be a positive integer. A set of strings $S$ is a _good string set_ when the following conditions hold true:\n\n*   Each string in $S$ has a length between $1$ and $L$ (inclusive) and consists of the characters `0` and `1`.\n*   Any two distinct strings in $S$ are prefix-free.\n\nWe have a good string set $S = { s_1, s_2, ..., s_N }$. Alice and Bob will play a game against each other. They will alternately perform the following operation, starting from Alice:\n\n*   Add a new string to $S$. After addition, $S$ must still be a good string set.\n\nThe first player who becomes unable to perform the operation loses the game. Determine the winner of the game when both players play optimally.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^5$\n*   $1 \\leq L \\leq 10^{18}$\n*   $s_1$, $s_2$, ..., $s_N$ are all distinct.\n*   { $s_1$, $s_2$, ..., $s_N$ } is a good string set.\n*   $|s_1| + |s_2| + ... + |s_N| \\leq 10^5$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $L$\n$s_1$\n$s_2$\n$:$\n$s_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc087_c","tags":[],"sample_group":[["2 2\n00\n01","Alice\n\nIf Alice adds `1`, Bob will be unable to add a new string."],["2 2\n00\n11","Bob\n\nThere are two strings that Alice can add on the first turn: `01` and `10`. In case she adds `01`, if Bob add `10`, she will be unable to add a new string. Also, in case she adds `10`, if Bob add `01`, she will be unable to add a new string."],["3 3\n0\n10\n110","Alice\n\nIf Alice adds `111`, Bob will be unable to add a new string."],["2 1\n0\n1","Bob\n\nAlice is unable to add a new string on the first turn."],["1 2\n11","Alice"],["2 3\n101\n11","Bob"]],"created_at":"2026-03-03 11:01:13"}}