Score : $400$ points

问题陈述

有一个 $H$ 行 $W$ 列的网格。用 $(i, j)$ 表示从顶部数第 $i$ 行，从左边数第 $j$ 列的单元格。 最初，每个单元格中都有一堵墙。 在按照给定顺序处理了 $Q$ 个查询后，找出剩余的墙的数量。

在第 $q$ 个查询中，你将得到两个整数 $R_q$ 和 $C_q$。 你在 $(R_q, C_q)$ 放置一个炸弹来摧毁墙。结果，会发生以下过程。

• 如果 $(R_q, C_q)$ 处有墙，摧毁那堵墙并结束过程。
• 如果 $(R_q, C_q)$ 处没有墙，摧毁从 $(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)$ 处的墙。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

There is a grid with $H$ rows and $W$ columns. Let $(i, j)$ denote the cell at the $i$-th row from the top and $j$-th column from the left.
Initially, there is one wall in each cell.
After processing $Q$ queries explained below in the order they are given, find the number of remaining walls.

In the $q$-th query, you are given two integers $R_q$ and $C_q$.
You place a bomb at $(R_q, C_q)$ to destroy walls. As a result, the following process occurs.

• If there is a wall at $(R_q, C_q)$, destroy that wall and end the process.
• If there is no wall at $(R_q, C_q)$, destroy the first walls that appear when looking up, down, left, and right from $(R_q, C_q)$. More precisely, the following four processes occur simultaneously:
  • If there exists an $i \lt R_q$ such that a wall exists at $(i, C_q)$ and no wall exists at $(k, C_q)$ for all $i \lt k \lt R_q$, destroy the wall at $(i, C_q)$.
  • If there exists an $i \gt R_q$ such that a wall exists at $(i, C_q)$ and no wall exists at $(k, C_q)$ for all $R_q \lt k \lt i$, destroy the wall at $(i, C_q)$.
  • If there exists a $j \lt C_q$ such that a wall exists at $(R_q, j)$ and no wall exists at $(R_q, k)$ for all $j \lt k \lt C_q$, destroy the wall at $(R_q, j)$.
  • If there exists a $j \gt C_q$ such that a wall exists at $(R_q, j)$ and no wall exists at $(R_q, k)$ for all $C_q \lt k \lt j$, destroy the wall at $(R_q, j)$.

Constraints

• $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$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$H$ $W$ $Q$

$R_1$ $C_1$

$R_2$ $C_2$

$\vdots$

$R_Q$ $C_Q$

Output

Print the number of remaining walls after processing all queries.

Sample Input 1

2 4 3
1 2
1 2
1 3

Sample Output 1

2

The process of handling the queries can be explained as follows:

• In the 1st query, $(R_1, C_1) = (1, 2)$. There is a wall at $(1, 2)$, so the wall at $(1, 2)$ is destroyed.
• In the 2nd query, $(R_2, C_2) = (1, 2)$. There is no wall at $(1, 2)$, so the walls at $(2,2),(1,1),(1,3)$, which are the first walls that appear when looking up, down, left, and right from $(1, 2)$, are destroyed.
• In the 3rd query, $(R_3, C_3) = (1, 3)$. There is no wall at $(1, 3)$, so the walls at $(2,3),(1,4)$, which are the first walls that appear when looking up, down, left, and right from $(1, 3)$, are destroyed.

After processing all queries, there are two remaining walls, at $(2, 1)$ and $(2, 4)$.

Sample Input 2

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

Sample Output 2

10

Sample Input 3

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

Sample Output 3

2