🐰😺🎨 兔猫信奥学院的魔法画板探秘 🎨😺🐰

小西最近迷上了在魔法画板上涂色。画板是一个 (n) 行 (m) 列的网格，每个格子初始都是空白。为了锻炼耐心，他准备执行 (q) 次涂色任务。每次任务要么在某一行上“涂”上一层颜色，要么在某一列上“涂”上一层颜色。

但小西不喜欢层层叠叠的涂色：只要某个格子的涂色层数达到 (k) 层，他就会把这个格子的颜色“全部擦除”，让它重新变为空白（即层数归零）。

现在请你帮小西算一算：在完成所有 (q) 次操作之后，画板上还有多少格是“非空白”的（即涂色层数不为 0）？

输入格式

n m q k
op_1 x_1
op_2 x_2
...
op_q x_q

• 第一行四个正整数
  • \(n, m\) (\(1 \le n, m \le 2\times10^5\))：行数和列数；
  • \(q\) (\(1 \le q \le 5\times10^5\))：操作次数；
  • \(k\) (\(1 \le k \le 5\times10^5\))：达到 (k) 层即擦除。
• 接下来 \(q\) 行，每行两个整数
  • op ((1) 或 (2))：操作类型，
    • 若 op = 1，则给第 x 行的每个格子上色一层；
    • 若 op = 2，则给第 x 列的每个格子上色一层。
  • (x)（保证在合法范围内）：行号或列号，均为 1 到相应维度。

输出格式

ans

• 一行一个整数，表示所有操作结束后画板上“非空白”格子的总数。

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

3

解释

• 操作 1：涂第 1 行 → 行涂层数 ([1,1,1])
• 操作 2：涂第 1 列 → 列涂层数 ([1;0])
• 操作 3：再涂第 1 行 → 行层数 ([2,2,2])
• 操作 4：涂第 2 列 → 列层数 ([0;1])
  每个格子最终层数为 “行层数 + 列层数”，再对 (k=3) 取模：

(2+1)%3=0,  (2+0)%3=2,  (2+0)%3=2
(0+1)%3=1,  (0+0)%3=0,  (0+0)%3=0

非零格子共 3 个。

数据范围

• \(1 \le n,m \le 2\times10^5\)
• \(1 \le q \le 5\times10^5\)
• \(1 \le k \le 5\times10^5\)
• op ∈ {1,2}，所有行号、列号均合法。