OA: Connect-N on an unbounded board

A Connect-style game runs on a board with no edges. Columns are any integers, including negative ones, and every column is as tall as needed. Pieces are dropped into a column and fall to the lowest empty row. Row 0 is the bottom.

Build ConnectN(n), where n >= 1. (The constructor also takes a diagonals flag, which level 2 uses. At this level it is always False: ignore it.)

• insert(col, player) -> player | None: drops player's piece (any hashable, e.g. "X") into col. Returns player if the new piece is now part of an unbroken line of at least n of that player's pieces, horizontally or vertically. Otherwise returns None. The game doesn't stop after a win; later inserts are judged the same way.
• height(col) -> int: how many pieces are in col.

Columns fill up unevenly, so a row can have holes where a neighbouring column is too short. A hole breaks a horizontal line.

Each insert must be O(n), however big the board gets: with small n, a row of 40,000 pieces must not make each insert walk the whole row.

g = ConnectN(3)
g.insert(0, "X")    # None
g.insert(1, "X")    # None
g.insert(1, "O")    # None   (sits on top of X in column 1, row 1)
g.insert(2, "X")    # "X"   row 0: columns 0, 1, 2
g.insert(5, "O")    # None   (column 5, row 0: far from anything)