Bottom-Insertion Connect Game: Detect the First k-in-a-Row Winner

Two players, B and R, take turns dropping pieces onto a board that covers the upper half-plane of an integer grid. Columns are indexed by arbitrary integers (..., -2, -1, 0, 1, 2, ...), and rows are indexed 0, 1, 2, ... counting upward from the bottom.

A move is described by a pair (player, column) and is applied as follows:

• If the chosen column is empty, the new piece is placed at row 0 (the bottom cell of that column).
• If the column already contains pieces, every piece in that column is pushed up by one row, and the new piece is placed at row 0.

Pieces never move sideways, and a move never affects any column other than the one played.

Given a positive integer k and a chronological list of moves, process the moves one at a time. After a move is applied, a player wins if the board contains k consecutive occupied cells in a single row or in a single column that all hold that player's pieces. Diagonal lines do not count. Because a move shifts an entire column upward, a single move can change the row alignment of many pieces at once — so one move can simultaneously create winning lines for both players.

Determine the result of the game:

• If at least one player has a winning line after some move, stop at the first such move and return [m, winners], where m is the 1-based index of that move and winners is the alphabetically sorted list of all players who hold a winning line at that moment (["B"], ["R"], or ["B", "R"]).
• If no player has a winning line after all moves have been applied, return [-1, []].

Input

• k — an integer, the required run length.
• moves — a list of moves in the order they are played; each move is a pair [player, column], where player is the string "B" or "R" and column is an integer.

Output

A pair [m, winners] as described above: the 1-based index of the first winning move and the alphabetically sorted list of winners at that moment, or [-1, []] if nobody wins.

Constraints

• 1 <= k <= 50
• 1 <= len(moves) <= 5000
• -10^6 <= column <= 10^6 (the board is unbounded — do not assume a fixed width)
• player is always "B" or "R"

Example 1

k = 3
moves = [["B", 0], ["R", 5], ["B", 1], ["R", 5], ["B", 2]]

Output: [5, ["B"]]

After move 5, row 0 contains B pieces in columns 0, 1, and 2 — three consecutive B cells in a row, so B wins on move 5. (Column 5 holds two R pieces, which is not enough for k = 3.)

Example 2

k = 3
moves = [["R", -1], ["B", -1], ["R", 0], ["B", 0], ["R", 1], ["B", 1]]

Output: [6, ["B", "R"]]

Each B move pushes the R piece in that column up to row 1 and lands at row 0. After move 6, row 0 contains B in columns -1, 0, 1 and row 1 contains R in columns -1, 0, 1. Both players complete a run of 3 on the same move, so both win simultaneously.

Example 3

k = 3
moves = [["B", 0], ["R", 0], ["B", 0]]

Output: [-1, []]

All three pieces land in column 0. From bottom to top the column reads B, R, B (each new piece is inserted at the bottom, pushing the older pieces up), so there is no run of 3 anywhere and nobody wins.