CF325D.Reclamation

In a far away land, there exists a planet shaped like a cylinder. There are three regions in this planet: top, bottom, and side as shown in the following picture.

Both the top and the bottom areas consist of big cities. The side area consists entirely of the sea.

One day, a city decides that it has too little space and would like to reclamate some of the side area into land. The side area can be represented by a grid with r rows and c columns — each cell represents a rectangular area in the side area. The rows are numbered 1 through r from top to bottom, while the columns are numbered 1 through c from left to right. Two cells are adjacent if they share a side. In addition, two cells located on the same row — one in the leftmost column, and the other in the rightmost column — are also adjacent.

Initially, all of the cells are occupied by the sea. The plan is to turn some of those cells into land one by one in a particular order that will be given to you.

However, the sea on the side area is also used as a major trade route. More formally, it is not allowed to reclamate the sea cells into land in such way that there does not exist a sequence of cells with the following property:

• All cells in the sequence are occupied by the sea (i.e., they are not reclamated).
• The first cell in the sequence is in the top row.
• The last cell in the sequence is in the bottom row.
• Consecutive cells in the sequence are adjacent.

Thus, the plan is revised. Each time a cell is going to be turned from sea to land, the city first needs to check whether or not it would violate the above condition by doing that. If it would, then the cell is not turned into land and the plan proceeds into the next cell. Otherwise, the cell is turned into land.

Your job is to simulate this and output the number of cells that were successfully turned into land.

在遥远的星系中，存在着一颗形状为圆柱体的行星。该行星分为三个区域：顶部、底部和侧面，如下图所示。

顶部与底部区域均由大型城市构成；而侧面区域则完全由海洋覆盖。

某日，一座城市认为自身可用空间过小，希望将部分侧面区域填海造陆。侧面区域可建模为一个具有 $r$ 行 $c$ 列的网格——每个格子代表侧面区域中一块矩形区域。行号从上至下依次编号为 $1$ 至 $r$，列号从左至右依次编号为 $1$ 至 $c$。若两个格子共享一条边，则称它们相邻；此外，同一行中位于最左列与最右列的两个格子也被视为相邻。

初始时，所有格子均被海洋占据。填海计划将按给定顺序，逐个将某些格子由海洋转变为陆地。

然而，侧面区域的海洋同时也是重要的贸易航道。更准确地说，不允许以如下方式实施填海：导致不存在满足以下全部条件的格子序列：

• 序列中所有格子均被海洋占据（即尚未被填海）；
• 序列的第一个格子位于最顶行（第 $1$ 行）；
• 序列的最后一个格子位于最底行（第 $r$ 行）；
• 序列中任意两个连续格子彼此相邻。

因此，填海计划需进行调整：每次尝试将某个格子由海洋变为陆地前，城市必须首先检验该操作是否会违反上述条件。若会违反，则跳过该格子，不进行填海，并继续处理下一个格子；否则，执行填海操作，将该格子变为陆地。

你的任务是模拟这一过程，并输出最终成功填海的格子总数。

The first line consists of three integers r, c, and n (1 ≤ r, c ≤ 3000, 1 ≤ n ≤ 3·105). Then, n lines follow, describing the cells in the order you will reclamate them. Each line will consists of two integers: r__i and c__i (1 ≤ r__i ≤ r, 1 ≤ c__i ≤ c), which represents the cell located at row r__i and column c__i. All of the lines describing the cells will be distinct.

第一行包含三个整数 $r$、$c$ 和 $n$（$1 \leq r,\,c \leq 3000$，$1 \leq n \leq 3\cdot10^5$）。随后是 $n$ 行，按你将要进行复垦的顺序描述各个单元格。每行包含两个整数：$r_i$ 和 $c_i$（$1 \leq r_i \leq r$，$1 \leq c_i \leq c$），表示位于第 $r_i$ 行、第 $c_i$ 列的单元格。所有描述单元格的行均互不相同。

You should output a single number representing the number of cells that were successfully turned to land.

你应该输出一个数字，表示成功变为陆地的单元格数量。

The pictures below show the sequence of reclamations that are performed in the example input. Blue cells represent the cells occupied by sea, while other colored cells represent land. The latest cell that are reclamated is colored either yellow or red, depending on whether the addition violates the condition in the statement. The dashed red line represents a possible trade route, if it exists.

No route exists, so this reclamation is not performed.

No route exists, skipped.

Remember that the leftmost and rightmost cells in the same row are adjacent.

No route exists, skipped.

Hence the result is:

There are 6 successful reclamation and 3 failed ones.

下图展示了示例输入中执行的填海造陆操作序列。蓝色单元格表示被海水占据的单元格，其他颜色的单元格表示陆地。最新填海造陆的单元格被染成黄色或红色，具体取决于该次添加是否违反题目中的条件。虚线红色线条表示一条可能存在的贸易航线（若存在的话）。

不存在可行航线，因此此次填海造陆不执行。

不存在可行航线，跳过。

注意：同一行中最左侧与最右侧的单元格是相邻的。

不存在可行航线，跳过。

因此最终结果为：

其中成功填海造陆共 6 次，失败共 3 次。