Little C is coloring an $n \times m$ grid with colored pencils. Initially, all cells are blank.

He performs $q$ coloring operations. Each operation involves selecting either a row or a column and adding $1$ layer of color to all cells in that row or column.

Little C likes light colors, so after each operation, he erases the color from all cells that have reached $k$ layers of color, making those cells blank again.

Little C wants to know how many cells have color on them at the end.

Input

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

Output a single integer representing the total number of cells that have color on them at the end.

Examples

Input 1

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

Output 1

8

Note 1

The cell at row $1$, column $1$ has no color. The cell at row $1$, column $2$ has $1$ layer of color. The cell at row $1$, column $3$ has no color. The cell at row $1$, column $4$ has $1$ layer of color.

The cell at row $2$, column $1$ has $1$ layer of color. The cell at row $2$, column $2$ has $2$ layers of color. The cell at row $2$, column $3$ has $1$ layer of color. The cell at row $2$, column $4$ has $2$ layers of color.

The cell at row $3$, column $1$ has $2$ layers of color. The color of the cell at row $3$, column $2$ is erased. The cell at row $3$, column $3$ has $2$ layers of color. The color of the cell at row $3$, column $4$ is also erased.

In the end, there are $8$ cells with color.

Examples 2-4

See paint/paint2.in and paint/paint2.ans, paint/paint3.in and paint/paint3.ans, and paint/paint4.in and paint/paint4.ans in the additional files. These examples satisfy the constraints of test cases $1$, $5$, and $20$ respectively.

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: Guaranteed $op=1$.

Special Property B: Guaranteed $k=2$.