Design Generalized Tic-Tac-Toe

Design Generalized Tic-Tac-Toe Implement a two-player Tic-Tac-Toe game on an arbitrary board: class TicTacToe: def __init__(self, m: int, n: int, k: int): ... def move(self, row: int, col: int, player: int) -> int: ... The board has m rows and n columns. A player wins by placing at least k consecutive marks horizontally, vertically, diagonally, or anti-diagonally. player is either 1 or 2. Every move is guaranteed valid. Return 0 when nobody wins, otherwise return the winning player's id. Input format The first line contains m n k q. Each of the next q lines contains row col player. Print the result of every move. Constraints 1 <= m, n <= 10^4 1 <= q <= min(m × n, 2 × 10^5) At most 2 × 10^5 cells are occupied. Example Input 3 3 3 5 0 0 1 1 0 2 0 1 1 1 1 2 0 2 1 Output 0 0 0 0 1