该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一个 $H$ 行 $W$ 列的网格。用 $(i,j)$ 表示从上往下第 $i$ 行，从左往右第 $j$ 列的单元格。

最初，每个单元格中都有一面墙。我们将依次处理 $Q$ 个查询，每个查询会破坏一些墙。请计算处理完所有查询后，剩余的墙的数量。

在第 $q$ 个查询中，我们得到两个整数 $R_q$ 和 $C_q$，表示在位置 $(R_q,C_q)$ 放置一枚炸弹。炸弹会按照以下规则摧毁墙壁：

1. 如果位置 $(R_q,C_q)$ 有墙：

   • 摧毁该位置的墙，然后结束此次查询

2. 如果位置 $(R_q,C_q)$ 没有墙：

   • 同时向上、下、左、右四个方向查看，摧毁在每个方向上遇到的第一面墙
   • 具体来说，以下四个过程会同时进行：
     • 向上：如果存在 $i < R_q$，使得 $(i,C_q)$ 处有墙，且对于所有 $i < k < R_q$，$(k,C_q)$ 处都没有墙，则摧毁 $(i,C_q)$ 处的墙
     • 向下：如果存在 $i > R_q$，使得 $(i,C_q)$ 处有墙，且对于所有 $R_q < k < i$，$(k,C_q)$ 处都没有墙，则摧毁 $(i,C_q)$ 处的墙
     • 向左：如果存在 $j < C_q$，使得 $(R_q,j)$ 处有墙，且对于所有 $j < k < C_q$，$(R_q,k)$ 处都没有墙，则摧毁 $(R_q,j)$ 处的墙
     • 向右：如果存在 $j > C_q$，使得 $(R_q,j)$ 处有墙，且对于所有 $C_q < k < j$，$(R_q,k)$ 处都没有墙，则摧毁 $(R_q,j)$ 处的墙

输入格式

第一行包含三个整数 $H,W,Q$，分别表示网格的行数、列数和查询数量。

接下来 $Q$ 行，每行包含两个整数 $R_q,C_q$，表示第 $q$ 个查询中炸弹放置的位置。

输出格式

输出一个整数，表示处理完所有查询后剩余的墙的数量。

样例

2 4 3
1 2
1 2
1 3

2

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

10

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

2

提示

样例 #1 解释

让我们按顺序处理查询：

1. 第一个查询 $(R_1,C_1)=(1,2)$：

   • 该位置有墙，直接摧毁这面墙

2. 第二个查询 $(R_2,C_2)=(1,2)$：

   • 该位置没有墙，向四个方向寻找并摧毁最近的墙
   • 摧毁了 $(2,2),(1,1),(1,3)$ 处的墙

3. 第三个查询 $(R_3,C_3)=(1,3)$：

   • 该位置没有墙，向四个方向寻找并摧毁最近的墙
   • 摧毁了 $(2,3),(1,4)$ 处的墙

最终只剩下 $(2,1)$ 和 $(2,4)$ 两面墙。

数据范围

• $1 \leq H,W$
• $H \times W \leq 4 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq R_q \leq H$
• $1 \leq C_q \leq W$
• 所有输入均为整数