You are asked to implement a variant of the classic Connect Four game, played on an unbounded board. ## Game Rules - The board consists of vertical columns indexed by integers. Columns extend **infinitely in both horizontal directions**, so any integer (including negative values) is a valid column index. - Each column is also **unbounded vertically**: it can hold any number of pieces. - Pieces are dropped into a column from above and fall under **gravity**: a piece inserted into column `col` lands on top of the pieces already in that column. If a column currently holds `h` pieces, the new piece occupies row `h` of that column (rows are 0-indexed from the bottom, so the bottom cell of every column is row 0). - Two or more players take part; each player is identified by an integer ID. - A player **wins** as soon as they have `N` of their own pieces in a line of consecutive cells, either: - **vertically** — `N` consecutive pieces stacked in the same column, or - **horizontally** — `N` pieces in the same row across `N` consecutive columns. Note that because columns fill independently, adjacent columns can have very different heights (the board is sparsely occupied). A horizontal line at row `r` only counts a column if that column actually has a piece at row `r` and that piece belongs to the player — an empty cell or an opponent's piece breaks the run. ## Task Implement a game class supporting: - `ConnectN(n)` — initialize the game where a player needs `n` in a row to win. - `insert(col, player)` — drop a piece for `player` into column `col`, and return `true` if this move gives `player` `N` in a row (vertically or horizontally), otherwise `false`. You will be given a sequence of moves and must report, for each move, whether it wins the game. Process every move in the sequence even after a win has occurred (each move is judged independently by the rule above). ## Performance Requirement The board is unbounded, so scanning the whole board after every move is not acceptable. Each `insert` must only examine the cells that the new piece could possibly affect: the top of its own column and the cells within distance `N - 1` of the new piece in its row. Your solution should handle up to $10^5$ moves efficiently, with each move costing $O(N)$ time (or better) and total memory proportional to the number of pieces placed. ## Input Format - The first line contains two integers `n` and `m` — the win length ($2 \le n \le 1000$) and the number of moves ($1 \le m \le 10^5$). - Each of the next `m` lines contains two integers `col` and `player` — the column ($-10^9 \le col \le 10^9$) and the player ID ($1 \le player \le 10^9$). ## Output Format For each move, in order, output `true` if that move creates a run of at least `n` consecutive pieces (vertically or horizontally) for the moving player, and `false` otherwise — one value per line. ## Example Input: ``` 3 7 0 1 1 2 1 1 2 2 -1 1 2 1 -1 1 ``` Output: ``` false false false false false false false ``` Walkthrough of the final board state (rows shown bottom-up): ``` row 1: . 1 1 row 0: 1 1 2 2 col: -1 0 1 2 ``` - Move 5 (`-1, 1`): player 1 now has pieces at row 0 in columns -1 and 0, but column 1 holds player 2's piece at row 0, so the horizontal run is only 2 — not a win for `n = 3`. - Move 6 (`2, 1`): the piece lands at row 1 of column 2. In row 1, only columns 1 and 2 are occupied by player 1 — a run of 2, not a win. Column 2 vertically holds `[2, 1]` — no vertical run either. A second example where a win occurs: Input: ``` 3 5 0 1 0 1 5 2 0 1 5 2 ``` Output: ``` false false false true false ``` The fourth move stacks player 1's third consecutive piece in column 0 (rows 0, 1, 2), completing a vertical run of length 3.