题目描述
小 C 正在用彩铅给一张 $n$ 行 $m$ 列的方格纸涂色。初始时，所有方格都是空白的。
他一共要进行 $q$ 次涂色，每次涂色会选取一行或一列，给这一行或这一列的所有方格都添加 $1$ 层颜色。
小 C 喜欢浅色，所以他会在每次涂色结束后，把所有被涂上 $k$ 层颜色的方格的颜色都擦掉，让这些方格都变成空白的。
小 C 想知道，在最终共有多少方格被涂上了颜色。
输入格式
第一行四个整数 $n,m,q,k$。
接下来 $q$ 行，每行两个整数 $op,x$。
- 若 $op=1$，则表示给第 $x$ 行的所有方格都添加 $1$ 层颜色；
- 若 $op=2$，则表示给第 $x$ 列的所有方格都添加 $1$ 层颜色。
输出格式
一个整数，表示在最终共有多少方格被涂上了颜色。
样例 1 输入
3 4 5 3 1 3 2 4 1 2 1 3 2 2
样例 1 输出
8
样例 1 解释
第 $1$ 行第 $1$ 列的方格没有被涂上颜色，第 $1$ 行第 $2$ 列的方格被涂上了 $1$ 层颜色，第 $1$ 行第 $3$ 列的方格没有被涂上颜色，第 $1$ 行第 $4$ 列的方格被涂上了 $1$ 层颜色；
第 $2$ 行第 $1$ 列的方格被涂上了 $1$ 层颜色，第 $2$ 行第 $2$ 列的方格被涂上了 $2$ 层颜色，第 $2$ 行第 $3$ 列的方格被涂上了 $1$ 层颜色，第 $2$ 行第 $4$ 列的方格被涂上了 $2$ 层颜色；
第 $3$ 行第 $1$ 列的方格被涂上了 $2$ 层颜色，第 $3$ 行第 $2$ 列的方格的颜色被擦掉了，第 $3$ 行第 $3$ 列的方格被涂上了 $2$ 层颜色，第 $3$ 行第 $4$ 列的方格的颜色也被擦掉了；
最终，共有 $8$ 个方格被涂上了颜色。
样例 2
见附加文件中的 paint/paint2.in 与 paint/paint2.ans。
该样例满足测试点 $1$ 的限制。
样例 3
见附加文件中的 paint/paint3.in 与 paint/paint3.ans。
该样例满足测试点 $5$ 的限制。
样例 4
见附加文件中的 paint/paint4.in 与 paint/paint4.ans。
该样例满足测试点 $20$ 的限制。
数据范围
对于 $100\%$ 的数据，$1 \le n,m \le 2\times 10^5$，$1 \le k \le q \le 5 \times 10^5$，$op \in \{1,2\}$，保证当 $op=1$ 时 $1 \le x \le n$，当 $op=2$ 时 $1 \le x \le m$。
| 测试点编号 | $n,m \le$ | $q \le$ | 特殊性质 |
|---|---|---|---|
| $1\sim4$ | $3000$ | $3000$ | 无 |
| $5\sim9$ | $3000$ | $5\times10^5$ | 无 |
| $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$ | 无 |
特殊性质 A：保证 $op=1$。
特殊性质 B：保证 $k=2$。