问题描述

Giga Code君买了一栋房子。这个房子被分为 $H \times W$ 个区域，水平方向上有 $H$ 个划分，竖直方向上有 $W$ 个划分。其中，第 $i$ 列第 $j$ 行的格子用 $(i, j)$ 表示。

其中有 $N$ 个区域放置了物品。第 $i$ 个物品占据了区域 $(r_i, c_i)$ 的全部。并且这些物品不会移动。

Giga Code君决定在这个房子里安置一个壁橱。壁橱必须是一个与房子外墙平行的长方形，并且壁橱所在的区域不能放置物品。然而，由于壁橱在发生地震时移动不便，所以他决定选择满足以下条件的摆放方式之一：

• 无论如何将壁橱移动，无法触碰到物品或者房子的外墙。

例如，可以摆放出如下的壁橱配置：

但是，无法摆放满足条件的壁橱配置如下：

请计算满足条件的壁橱配置有多少种。

约束条件

• $1 \leq H \leq 5,000$
• $1 \leq W \leq 5,000$
• $0 \leq N \leq 201,900$
• $1 \leq r_i \leq H$
• $1 \leq c_i \leq W$
• 这 $N$ 个物品被放置在不同的区域
• 所有的输入都是整数

部分问题

这个问题被拆分为若干个子问题，只有当所有子任务都得到正确解答时，才能视为"解决了这个子问题"。 给出的源代码得分等于通过的子任务的得分之和。

1. (2 分) $H = 1, W = 1$
2. (11 分) $H = 1, W \leq 25$
3. (11 分) $H \leq 25, W \leq 25$
4. (19 分) $N \leq 10$
5. (16 分) $H \leq 100, W \leq 100$
6. (17 分) $H \leq 350, W \leq 350$
7. (19 分) $H \leq 1500, W \leq 1500$
8. (5 分) 没有额外的约束条件

---

输入

输入从标准输入中按以下格式给出。

$H$ $W$ $N$ $r_1$ $c_1$ $r_2$ $c_2$ ... $r_N$ $c_N$

输出

请输出满足即使发生地震也不会动的壁橱配置的数量。

注意事项

由于输入规模较大，建议使用快速输入输出（例如 C++ 的 scanf/printf）

---

输入范例 1

3 3
2
1 1
3 2

输出范例 1

4

这个示例中，有 $4$ 种壁橱配置方式，请输出 "4"。

---

输入范例 2

1 10
3
1 1
1 5
1 8

输出范例 2

3

这个示例符合小任务 2 的条件。一共有 $3$ 种壁橱配置方式。

---

输入范例 3

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

输出范例 3

11

这个示例中，有 $11$ 种壁橱配置方式。可以自己尝试计数一下！

---

输入范例 4

4802 5000
10
254 3330
1713 3331
1712 989
256 988
4192 3521
3602 4991
255 987
3603 3520
256 987
4191 4992

输出范例 4

32

这个示例满足小任务 4 的条件。需要注意到小任务 4 中的 $H, W$ 可能较大。