{"problem":{"name":"Mex Game","description":{"content":"You are given a string of length $N+1$ consisting of `A` and `B`: $S = S_0\\cdots S_N$. For each $k=1, \\ldots, N$, solve the following problem. > Alice and Bob will play a game using a set $X$, which ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc063_a"},"statements":[{"statement_type":"Markdown","content":"You are given a string of length $N+1$ consisting of `A` and `B`: $S = S_0\\cdots S_N$. For each $k=1, \\ldots, N$, solve the following problem.\n\n> Alice and Bob will play a game using a set $X$, which is initially empty. For $t=1,\\ldots, k$ in this order, they will do the following action:\n> \n> *   if $t$ is odd, Alice will choose a non-negative integer $x$ and replace $X$ with $X\\cup {x}$;\n> *   if $t$ is even, Bob will choose a non-negative integer $x$ and replace $X$ with $X\\cup {x}$.\n> \n> Let $x$ be $\\mathrm{mex}(X)$ after all $k$ actions. If the character $S_x$ is `A`, Alice wins; if $S_x$ is `B`, Bob wins. Note that $X$ has at most $k$ elements, so $x = \\mathrm{mex}(X) \\leq k$ and the character $S_x$ exists.\n> Print the name of the winner when both players play optimally.\n\nWhat is $\\mathrm{mex}(X)$? For a finite set $X$ consisting of non-negative integers, $\\mathrm{mex}(X)$ is the smallest non-negative integer $x$ such that $x\\notin X$.\n\n## Constraints\n\n*   $1\\leq N\\leq 2\\times 10^5$\n*   $S$ is a string of length $N+1$ consisting of `A` and `B`.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc063_a","tags":[],"sample_group":[["2\nABB","Alice\nBob\n\nHere is a possible progression of the game with $k=1$.\n\n*   Alice chooses $x=10$.\n*   $\\mathrm{mex}(X)=\\mathrm{mex}(\\lbrace 10\\rbrace) = 0$, and $S_0$ is `A`, so Alice wins.\n\nHere is a possible progression of the game with $k=2$.\n\n*   Alice chooses $x=2$.\n*   Bob chooses $x=0$.\n*   $\\mathrm{mex}(X)=\\mathrm{mex}(\\lbrace 0,2\\rbrace) = 1$, and $S_1$ is `B`, so Bob wins."],["4\nAAAAA","Alice\nAlice\nAlice\nAlice"],["7\nBBAABABA","Bob\nBob\nAlice\nBob\nAlice\nBob\nAlice"]],"created_at":"2026-03-03 11:01:14"}}