Connect-N on an Infinite Board with Gravity

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.