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 L-shape (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).