John and Brus are playing a game where they alternate moves and John goes first. Initially, there is a string that contains only uppercase letters 'X', 'O' and 'L'. A move consists of replacing a single occurrence of 'X' with either 'O' or 'L'. After a player moves, if "LOL" (quotes for clarity) appears as a substring, that player immediately wins and the game ends. Otherwise, the game continues until there are no more 'X's left.
Both players use an optimal game strategy. If a player can win, he will follow the strategy that minimizes the number of moves in the game. Otherwise, if a player can make the game end without a winner, he will follow the strategy that does so (note that in this case the total number of moves in the game does not depend on the chosen strategy). Otherwise, if a player cannot win and cannot end the game in a draw, he will follow the strategy that maximizes the number of moves in the game.
You are given a String s containing the initial state of the game. If the game will end without a winner, return "Draw". If John will win the game, return "John x", and if Brus will win the game, return "Brus x", where x is the number of moves in the game, with no leading zeroes (all quotes for clarity). |