Implement a generalized Tic-Tac-Toe engine for two players on an `m x n` board with a configurable winning length `k`. The interview states the problem as a class: ```text TicTacToe(m, n, k) move(row, col, player) -> int ``` For grading, that class is driven by a single function. `generalized_tic_tac_toe(m, n, k, moves)` constructs a board with `m` rows and `n` columns and winning length `k`, then replays `moves` in order. Element `i` of `moves` is a triple `[row, col, player]` and stands for exactly one call `move(row, col, player)`. Return the list of the values those calls return, one per move, in move order. ## Rules - Players are identified by `1` and `2`. A move places that player's mark in cell `(row, col)`, which is empty immediately before the move. - A move returns `0` if nobody has won, `1` if player 1 has won, or `2` if player 2 has won. - A player wins when, after their mark is placed, they occupy at least `k` consecutive cells of one line through the newly placed cell. The four line directions are horizontal (same row), vertical (same column), main diagonal (down-right), and anti-diagonal (down-left). - "Consecutive" means no gap: every cell of the run holds that player's mark. A run longer than `k` also wins. If `k` is greater than the longest line this board has in some direction, that direction can never produce a win. - Rows are indexed `0` to `m - 1` from the top, columns `0` to `n - 1` from the left. - Players do not have to alternate; each move names the player who makes it. ## Output Return a list of integers whose length is exactly `len(moves)`, where element `i` is the value returned by move `i`. Every element is `0`, `1`, or `2`. When `moves` is empty, return an empty list. The answer is fully determined by the input, so there is no ordering or tie-breaking freedom anywhere. ## Examples **Example 1** ```text Input: m = 3, n = 4, k = 3, moves = [[1, 0, 1], [0, 0, 2], [1, 1, 1], [0, 1, 2], [1, 2, 1]] Output: [0, 0, 0, 0, 1] ``` Player 1 builds row 1 and player 2 builds row 0. After the fifth move player 1 holds `(1,0)`, `(1,1)` and `(1,2)` — three consecutive cells in row 1 — so that move returns `1`. Before it, neither player has more than two in a row anywhere. **Example 2** ```text Input: m = 1, n = 5, k = 3, moves = [[0, 0, 1], [0, 1, 1], [0, 3, 1], [0, 4, 1], [0, 2, 1]] Output: [0, 0, 0, 0, 1] ``` After four moves player 1 holds columns 0, 1, 3 and 4: two runs of length 2 separated by the still-empty column 2, so nothing wins. The fifth move fills column 2 and merges them into one run of length 5, which is at least `k = 3`, so it returns `1`. ## Guidance Only lines through the cell you just filled can turn from non-winning into winning, so aim for work proportional to the affected row, column and two diagonals rather than rescanning the whole board on every move. This is a performance goal, not part of the returned answer.