All submissions for this problem are available.
Read problem statement in Mandarin chinese and Vietnamese.After winning the Candidates Tournament, Suzumo is intensively training for his upcoming match against Magus Cartesian. In order to improve his calculation skills, Suzumo invented a new game, which he named PawnChess. PawnChess is a two-player game played on a row of $N$ cells. Its rules are as follows: - Initially, some pawns are placed in some cells; each pawn is either black or white. There may be at most one pawn in each cell at any time. For each white pawn, all the pawns that are to the left of this pawn are also white. - Let's call the players White and Black. Each player may only move pawns of their colour. The players alternate turns; White moves first. - In White's turn, White must move one pawn one cell to the right (if the pawn was in cell $i$, it is moved to cell $i+1$). Similarly, in Black's turn, Black must move one pawn one cell to the left (from cell $i$ to cell $i-1$). It is not allowed to move a pawn outside of the row of cells or to move a pawn to a cell which already contains a pawn with the same colour. - If a pawn $P$ is moved to an empty cell, nothing happens. If it is moved to a cell containing a pawn $R$ with the opposite colour, the pawn $R$ is captured — removed from the game, and $P$ is placed in the cell which previously contained $R$. - The winner of the game is the player that captures all the pieces of their opponent. Note that as long as there is at least one black and at least one white pawn, each player can make a move. Given the initial configuration of the game board, help Suzumo determine the winner of the game. Assume that both players play optimally. ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first and only line of each test case contains a single string $S$ with length $N$ describing the game board. Each character in $S$ is '.', 'W' or 'B' denoting an empty cell, a white pawn and a black pawn respectively. ### Output For each test case, print a single line containing the string `"W"` if White wins the game or `"B"` if Black wins. ### Constraints - $2 \le N \le 128$ - there is at least one white pawn and at least one black pawn - all pawns to the left of a white pawn are always white - the sum of $N$ over all test cases is at most $5 \cdot 10^5$ ### Example Input ``` 2 W..B WW.B ``` ### Example Output ``` W B ``` ### Explanation **Example case 2:** One possible sequence of moves is as follows: ``` WW.B W.WB W.B. .WB. .B.. ```
|Tags||alei, cook93, game-theory, games, medium|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.