# Implement Multi-Player Tic-Tac-Toe Implement a game class for an `N` by `N` board and `K` players. Each player has a distinct one-character printable mark. The constructor receives the marks in fixed turn order. ```text TicTacToe(n, player_marks) play(player, row, col) -> Status getStatus() -> Status ``` `player_marks` is a nonempty ordered list of distinct marks and its length is `K`. `player` is one of those marks. A `Status` is the JSON-safe object `{state, winner}`, where `state` is one of `INVALID`, `IN_PROGRESS`, `WIN`, or `TIE`; `winner` is the winning mark only when `state` is `WIN`, and is `null` otherwise. Players take turns in constructor order. `play` validates that the game is still active, it is that player's turn, `0 <= row < N` and `0 <= col < N`, and the cell is empty. A rejected move—including an out-of-bounds coordinate—returns `{state: INVALID, winner: null}` without changing the board, turn, or persistent game status. An accepted move returns the new persistent status. `getStatus()` returns only that persistent status, so it never returns `INVALID`. A player wins immediately after forming three consecutive marks horizontally, vertically, or along either diagonal. A run longer than three also wins. If the board becomes full with no winner, the result is `TIE`. ## Constraints - `3 <= N <= 200` - `2 <= K <= 16` - At most `N * N` accepted moves. - Aim to inspect only lines through the latest move. ## Example For `TicTacToe(3, [X, O])`, plays `X(0,0)`, `O(1,0)`, `X(0,1)`, `O(1,1)`, `X(0,2)` end with `{state: WIN, winner: X}`. ## Clarifications The winning length is fixed at three even when `N` is larger. Once a terminal status is reached, all later plays are invalid and `getStatus` remains terminal. ## Hints Only four directions through the newest mark need to be checked, expanding in both directions. ## Extensions - Reduce space when wins require an entire row, column, or diagonal. - Support undo and replay. - Generalize to a configurable winning length.