P17500 [ICPC 2026 Wuhan I] Rectangle Cutting

Yachiyo has a rectangle in the first quadrant of the Cartesian coordinate plane. The lower-left corner of the rectangle is at the origin $(0,0)$, and the upper-right corner is at $(n,m)$. In other words, the two sides of the rectangle are aligned with the $x$-axis and the $y$-axis, with lengths $n$ and $m$ along the $x$- and $y$-directions, respectively. Yachiyo decides to make $q$ cuts on this rectangle. Specifically, there are two kinds of cuts: - Horizontal cut: given a positive integer $k$, cut along the line $y=k$. - Vertical cut: given a positive integer $k$, cut along the line $x=k$. Each cut goes through the entire region, further dividing the existing rectangles into more smaller rectangles. Yachiyo wants to know, after each cut is completed, what the maximum area among all the currently divided small rectangles is.

The first line contains three integers $n,m,q$ ($1 \le n,m \le 10^9$, $1 \le q \le 5\times10^5$), representing the horizontal length, vertical length, and the number of cuts of the initial rectangle, respectively. The next $q$ lines each contain two integers $op,k$, describing one cut operation: - If $op=1$, it means a vertical cut is performed, and the given integer $k$ ($1 \le k

Output $q$ lines. The $i$-th line should contain one integer, representing the maximum area among all small rectangles after the $i$-th cut.

:::align{center}  Pic. 1: Sample explanation :::