Problem Description

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.

Input Format

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 Format

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

3 4 5 3
1 3
2 4
1 2
1 3
2 2

8

Hint

[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$.

Special property A: It is guaranteed that $op=1$.

Special property B: It is guaranteed that $k=2$.

Translated by ChatGPT 5