{"raw_statement":[{"iden":"problem statement","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$."},{"iden":"constraints","content":"*   $1\\leq N\\leq 2\\times 10^5$\n*   $S$ is a string of length $N+1$ consisting of `A` and `B`."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$S$"},{"iden":"sample input 1","content":"2\nABB"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"4\nAAAAA"},{"iden":"sample output 2","content":"Alice\nAlice\nAlice\nAlice"},{"iden":"sample input 3","content":"7\nBBAABABA"},{"iden":"sample output 3","content":"Bob\nBob\nAlice\nBob\nAlice\nBob\nAlice"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}