P9583 "MXOI Round 1" Coloring.

Xiao C is using colored pencils to color a grid paper with $n$ rows and $m$ columns. Initially, all cells are blank. He will perform $q$ coloring operations in total. In each operation, he chooses either a row or a column, and adds $1$ layer of color to every cell in that row or column. Xiao C likes light colors, so after each operation, he will erase the color of all cells that have been colored with exactly $k$ layers, making those cells blank again. Xiao C wants to know how many cells are colored in the end.

The first line contains four integers $n,m,q,k$. The next $q$ lines each contain two integers $op,x$. - If $op=1$, it means adding $1$ layer of color to all cells in row $x$; - If $op=2$, it means adding $1$ layer of color to all cells in column $x$.

Output one integer, indicating how many cells are colored in the end.

#### [Sample Explanation #1] The cell in row $1$, column $1$ is not colored; the cell in row $1$, column $2$ has $1$ layer of color; the cell in row $1$, column $3$ is not colored; the cell in row $1$, column $4$ has $1$ layer of color; The cell in row $2$, column $1$ has $1$ layer of color; the cell in row $2$, column $2$ has $2$ layers of color; the cell in row $2$, column $3$ has $1$ layer of color; the cell in row $2$, column $4$ has $2$ layers of color; The cell in row $3$, column $1$ has $2$ layers of color; the color of the cell in row $3$, column $2$ is erased; the cell in row $3$, column $3$ has $2$ layers of color; the color of the cell in row $3$, column $4$ is also erased; In the end, a total of $8$ cells are colored. #### [Sample #2] See `paint/paint2.in` and `paint/paint2.ans` in the attached files. This sample satisfies the constraints of test points $1$. #### [Sample #3] See `paint/paint3.in` and `paint/paint3.ans` in the attached files. This sample satisfies the constraints of test points $5$. #### [Sample #4] See `paint/paint4.in` and `paint/paint4.ans` in the attached files. This sample satisfies the constraints of test points $20$. #### [Constraints] For $100\%$ of the data, $1 \le n,m \le 2\times 10^5$, $1 \le k \le q \le 5 \times 10^5$, $op \in \{1,2\}$. It is guaranteed that when $op=1$, $1 \le x \le n$, and when $op=2$, $1 \le x \le m$. |Test point ID|$n,m \le$|$q \le$|Special property| |:---:|:---:|:---:|:---:| |$1\sim4$|$3000$|$3000$|None| |$5\sim9$|$3000$|$5\times10^5$|None| |$10\sim12$|$2\times10^5$|$5\times10^5$|A| |$13\sim16$|$2\times10^5$|$5\times10^5$|B| |$17\sim20$|$2\times10^5$|$5\times10^5$|None| Special property A: It is guaranteed that $op=1$. Special property B: It is guaranteed that $k=2$. Translated by ChatGPT 5