Two players play a game on a n*n chessboard. Starting with the first player, they take alternate turn putting figures on empty cells. During each turn, a player will place a figure on an empty cell in such a way that it can't be captured by any of the figures already on the board. Each figure can capture as a rook and as a knight. Rooks capture backwards, forwards, and sideways. Knights capture in an Lshape (two consecutive squares backwards, forwards, or sideways, and then one square in a perpendicular direction).
A player wins the game when the other player cannot make a move. You are given the first moves of such a game, and you are to determine who will win if both players are trying their best to win.
You are given a String[] moves representing the moves that have already been made. Each element of moves will be formatted as "xX", where x is a lowercase letter representing the vertical position and X is a number representing the horizontal position. Return one of three possible answers:
 "First player wins", if the first player will win or has already won (there are no valid moves left, and the first player made the last move).
 "Second player wins", if the second player will win or has already won (there are no valid moves left, and the second player made the last move).
 "Invalid input", if the input is invalid (a figure is placed on a previously occupied square, or a figure can be captured by another figure).
