Board Simulation: Bottom-Insert Pieces with Uniform Row and Column Detection

Board Simulation: Bottom-Insert Pieces with Uniform Row and Column Detection

You must simulate a 2-D game board with R rows and C columns. Each cell is either empty or holds a piece of one of two types, "A" or "B". Rows are numbered from 0 (the bottom row) to R - 1 (the top row); columns are numbered 0 to C - 1.

Insertion rule

Pieces are always inserted at the bottom of a column:

• When a piece p is inserted into column c, every piece already in column c shifts up by one row, and the new piece occupies the bottom cell (row 0, column c).
• Because pieces only enter from the bottom, the pieces in any column always occupy a contiguous block of rows starting at row 0.
• If column c already holds R pieces (the column is full), the insertion fails and the board state does not change.

Task

Process a sequence of insertion operations. Each operation is a pair (c, p) meaning "insert a piece of type p into column c". After processing each operation (whether it succeeded or failed), report three values describing the board state at that moment:

1. ok — true if the insertion succeeded, false if it failed because column c was already full.
2. uniform_column — true if any column is completely filled (all R cells occupied) with pieces of the same type; otherwise false.
3. uniform_row — true if any row is completely filled (all C cells in that row occupied) with pieces of the same type; otherwise false.

Return the list of these triples, one per operation, in order.

Input

• An integer R — the number of rows (1 <= R <= 50).
• An integer C — the number of columns (1 <= C <= 50).
• A list ops of operations, where each operation is [c, p] with 0 <= c < C and p equal to the string "A" or "B" (1 <= len(ops) <= 10^4).

Output

A list of len(ops) triples [ok, uniform_column, uniform_row] (booleans), where the i-th triple describes the board immediately after processing the i-th operation.

Example

Input:

R = 2, C = 2
ops = [[0, "A"], [1, "A"], [0, "B"], [1, "B"], [1, "A"]]

Output:

[[true, false, false],
 [true, false, true],
 [true, false, false],
 [true, false, true],
 [false, false, true]]

Explanation (rows listed bottom-up; . = empty):

1. add(0, "A"): column 0 becomes [A]. Board: row 0 = A .. No full column; row 0 is not fully occupied. -> [true, false, false]
2. add(1, "A"): column 1 becomes [A]. Row 0 = A A — fully occupied, all type A, so a uniform row exists. Neither column is full. -> [true, false, true]
3. add(0, "B"): the new B enters at the bottom of column 0 and pushes the existing A up, so column 0 is [B, A] (row 0 = B, row 1 = A). Column 0 is full but mixed. Row 0 = B A (mixed); row 1 = A . (not fully occupied). -> [true, false, false]
4. add(1, "B"): column 1 becomes [B, A]. Both columns are full but mixed. Row 0 = B B (uniform); row 1 = A A (uniform). -> [true, false, true]
5. add(1, "A"): column 1 is full, so the insertion fails and the board is unchanged. -> [false, false, true]

Notes

• A column counts as uniform only when all R of its cells are occupied by the same piece type; a partially filled column never counts, even if its current pieces all match.
• A row counts as uniform only when all C of its cells are occupied by the same piece type. Row r is fully occupied exactly when every column currently holds more than r pieces.
• Failed insertions must leave the board — and therefore the two uniformity flags — unchanged from the previous state.
• A brute-force O(R * C) scan after each operation is acceptable at these constraints, but an incremental solution that updates per-column and per-row bookkeeping in O(R) or better per operation is preferred.