Description

小 C 正在用彩铅给一张 n 行 m 列的方格纸涂色。初始时，所有方格都是空白的。

他一共要进行 q 次涂色，每次涂色会选取一行或一列，给这一行或这一列的所有方格都添加 1 层颜色。

小 C 喜欢浅色，所以他会在每次涂色结束后，把所有被涂上 k 层颜色的方格的颜色都擦掉，让这些方格都变成空白的。

小 C 想知道，在最终共有多少方格被涂上了颜色。

Input Format

第一行四个整数 n,m,q,k。

40% 

1<=n,m<=3e3. 1<=k<=q<=3e3

100%

1<=n,m<=2e5. 1<=k<=q<=5e5

接下来 q 行，每行两个整数 op,x。

若 op=1，则表示给第 x 行的所有方格都添加 1 层颜色；
若 op=2，则表示给第 x 列的所有方格都添加 1 层颜色。

Output Format

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

8

Source