Design a Tic-Tac-Toe System for k Players on an n×n Board with 3-in-a-Row Win Condition

Problem: Design a Tic-Tac-Toe System (k Players, n×n Board, 3-in-a-Row Wins) Design a game system that supports the rules below and returns the correct game status after every move. Given k players (e.g., player ids 1..k or names). An n × n board (n can be very large). Players take turns placing their marks; each move places one mark on an empty cell. Win Condition Regardless of how large n is, a player wins immediately once they form 3 consecutive marks in a straight line. Allowed directions: Horizontal Vertical Main diagonal (top-left to bottom-right) Anti diagonal (top-right to bottom-left) What you need to implement Design an interface/class that processes moves and returns game status. Operation move(player, row, col): player places a mark at (row, col). Return after each move If this move makes the player win: return "<player> won" If the board is full and nobody won: return "Game Over" If the game is still ongoing: return an in-progress status (e.g., "In Progress" / "Continue", define consistently) Constraints / Edge Cases (row, col) must satisfy 0 <= row, col < n. You cannot play on an occupied cell; define behavior (throw exception / return error). If the game has ended (someone won or Game Over), define behavior for subsequent move calls. Scale Expectations (recommended) n can be large, so avoid O(n^2) space for the whole board unless justified. Aim for low per-move time complexity and provide complexity analysis. Example Assume k=2, n=5: move(1, 0, 0) → In Progress move(2, 1, 0) → In Progress move(1, 0, 1) → In Progress move(2, 1, 1) → In Progress move(1, 0, 2) → "1 won" Test Cases (5) Assume outputs are In Progress / <player> won / Game Over. Horizontal win Input: k=2, n=5; moves=[(1,0,0),(2,1,0),(1,0,1),(2,1,1),(1,0,2)] Output: [In Progress, In Progress, In Progress, In Progress, "1 won"] Vertical win Input: k=2, n=5; moves=[(1,0,0),(2,0,1),(1,1,0),(2,1,1),(1,2,0)] Output: [In Progress, In Progress, In Progress, In Progress, "1 won"] Main diagonal win Input: k=2, n=5; moves=[(1,0,0),(2,0,1),(1,1,1),(2,0,2),(1,2,2)] Output: [In Progress, In Progress, In Progress, In Progress, "1 won"] Anti diagonal win Input: k=2, n=5; moves=[(1,0,2),(2,0,0),(1,1,1),(2,1,0),(1,2,0)] Output: [In Progress, In Progress, In Progress, In Progress, "1 won"] Board full, no winner Input: k=2, n=3; moves=[(1,0,0),(2,0,1),(1,0,2),(2,1,1),(1,1,0),(2,1,2),(1,2,1),(2,2,0),(1,2,2)] Output: [In Progress, In Progress, In Progress, In Progress, In Progress, In Progress, In Progress, In Progress, "Game Over"] Example Input k=2, n=5; moves=[(1,0,0),(2,1,0),(1,0,1),(2,1,1),(1,0,2)] Output [In Progress, In Progress, In Progress, In Progress, "1 won"]