Let’s rephrase the operation of pressing a stamp as follows:

• Initially, all cells are unused. When pressing stamp \((h,w)\), choose an \(h \times w\) rectangle consisting only of unused cells. Then, select one cell within the rectangle and mark it as used.

The cell where the color of stamp \((h,w)\) remains corresponds to the cell that is marked as used. The goal is to perform this operation for all stamps.

Let’s consider the properties of a valid sequence of operations.

In conclusion, the following properties hold:

• Property \(1\): At all stages of the operation, the region satisfies the following two conditions:

  • For each \(i\), the column numbers of unused cells in the \(i\)-th row form an interval \([l_i, r_i]\) (the interval may be empty). If these intervals are appropriately rearranged, \([l_{i_1}, r_{i_1}] \subseteq [l_{i_2}, r_{i_2}] \subseteq \cdots \subseteq [l_{i_N}, r_{i_N}]\).
  • For each \(j\), the row numbers of unused cells in the \(j\)-th column form an interval \([u_j, d_j]\) (the interval may be empty). If these intervals are appropriately rearranged, \([u_{j_1}, d_{j_1}] \subseteq [u_{j_2}, d_{j_2}] \subseteq \cdots \subseteq [u_{j_N}, d_{j_N}]\).

• Property \(2\): It is possible to take a rectangle of size \((h,w)\) within the unused region if and only if the stamp of size \((h,w)\) is unused.

We will demonstrate these properties by induction. Clearly, they hold in the initial state.

Consider pressing a stamp from an arbitrary state. First, the size of the stamp to be pressed must be maximal. Assume that a non-maximal stamp is pressed and the used cell is \((x,y)\). Then, considering a maximal rectangle containing cell \((x,y)\), it will no longer be possible to use the stamp of the same size as this rectangle. This would not result in a valid sequence of operations, so the size of the stamp to be pressed must always be maximal.

For the same reason, it is also impossible to use a cell that is included in two or more maximal rectangles.

Additionally, it is not possible to use cells other than the four corners of the rectangle. Consider the following state (where . represents a used cell). Suppose we are about to press a stamp on the top-left \(4 \times 5\) rectangle.

OOOOO.
OOOOOO
OOOOO.
OOOAO.
.OO...

What happens if we use cell \(A\) (\(=(4,4)\))? Using a stamp of size \(4 \times 4\) will no longer be possible, so this is not a valid operation. Generalizing this, we see that cells other than the four corners cannot be used.

Conversely, if we use a cell that is included in exactly one maximal rectangle and corresponds to one of the four corners, will it always be valid? In fact, it will be valid. If a cell satisfying the above conditions is used, the remaining unused cells will satisfy all the conditions initially presented.

Let’s return to the original problem. For the \(K\) stamps that have already been pressed, we need to appropriately determine which of the four corners was used to ensure the conditions above are met.

Suppose stamp \((h,w)\) is pressed at position \((a,b)\), and cell \((x,y)\) (\(x=a\) or \(a+h-1\), and \(y=b\) or \(b+w-1\)) is used. To obtain a valid operation, \((x,y)\) must satisfy the following conditions:

• At the stage where \(K\) stamps have been pressed, cell \((x,y)\) is not colored by another stamp.
• Just before pressing stamp \((h,w)\), cells \((x,b-1)\), \((x,b+w)\), \((a-1,y)\), and \((a+h,y)\) are used. Here, the cells that are out of the board are considered used.

We will represent the choice between \(x=a\) and \(x=a+h-1\) with a boolean variable. Similarly, the choice between \(y=b\) and \(y=b+w-1\) will also be represented with a boolean variable.

Then, all conditions can be written in the form of 2-SAT. So, we can solve this.

Let’s analyze the computational complexity. The number of variables and constraints in 2-SAT is \(O(K)\), so the complexity of this part is \(O(N^2)\). However, we need to determine the board state after pressing the initial \(K\) stamps, which takes \(O(N^3)\) (or any feasible complexity). Therefore, the final complexity is \(O(N^3)\).

Sample Implementation

Bonus: The tester’s solution is interesting.