CF1379F2.Chess Strikes Back (hard version)

Note that the difference between easy and hard versions is that in hard version unavailable cells can become available again and in easy version can't. You can make hacks only if all versions are solved.

Ildar and Ivan are tired of chess, but they really like the chessboard, so they invented a new game. The field is a chessboard $2n \times 2m$: it has $2n$ rows, $2m$ columns, and the cell in row $i$ and column $j$ is colored white if $i+j$ is even, and is colored black otherwise.

The game proceeds as follows: Ildar marks some of the white cells of the chessboard as unavailable, and asks Ivan to place $n \times m$ kings on the remaining white cells in such way, so that there are no kings attacking each other. A king can attack another king if they are located in the adjacent cells, sharing an edge or a corner.

Ildar would like to explore different combinations of cells. Initially all cells are marked as available, and then he has $q$ queries. In each query he either marks a cell as unavailable, or marks the previously unavailable cell as available. After each query he would like to know whether it is possible to place the kings on the available cells in a desired way. Please help him!

注意：简单版本与困难版本的区别在于，困难版本中不可用的格子可能再次变为可用，而简单版本中不可用的格子将始终保持不可用。仅当所有版本均被解决时，才允许进行 Hack。

伊尔达尔（Ildar）和伊万（Ivan）厌倦了国际象棋，但他们非常喜欢棋盘，因此发明了一种新游戏。游戏场地是一个 $2n \times 2m$ 的棋盘：它有 $2n$ 行、$2m$ 列；其中第 $i$ 行第 $j$ 列的格子，若 $i+j$ 为偶数则为白色，否则为黑色。

游戏规则如下：伊尔达尔将棋盘上部分白色格子标记为“不可用”，然后要求伊万在剩余的可用白色格子上放置 $n \times m$ 个国王（king），使得任意两个国王彼此不攻击。国王可以攻击与其位于相邻格子（即共享一条边或一个角）的其他国王。

伊尔达尔希望尝试不同的格子组合。初始时所有格子均标记为“可用”，随后他将执行 $q$ 次查询。每次查询中，他要么将某个格子标记为“不可用”，要么将之前标记为“不可用”的格子重新标记为“可用”。每次查询后，他都想知道：是否仍能在当前可用的白色格子上按要求放置这些国王？请帮助他！

The first line of input contains three integers $n$, $m$, $q$ ($1 \leq n, m, q \leq 200\,000$) — the size of the board and the number of queries.

$q$ lines follow, each of them contains a description of a query: two integers $i$ and $j$, denoting a white cell on the board ($1 \leq i \leq 2n$, $1 \leq j \leq 2m$, $i + j$ is even). If the cell $(i, j)$ was available before the query, then it becomes unavailable. Otherwise, if the cell was unavailable, it becomes available.

输入的第一行包含三个整数 $n$、$m$、$q$（$1 \leq n, m, q \leq 200\,000$）——分别表示棋盘的尺寸以及查询次数。

接下来有 $q$ 行，每行描述一个查询：两个整数 $i$ 和 $j$，表示棋盘上的一个白色格子（$1 \leq i \leq 2n$，$1 \leq j \leq 2m$，且 $i + j$ 为偶数）。若格子 $(i, j)$ 在本次查询前是可用的，则它变为不可用；否则（即该格子此前不可用），则它变为可用。

Output $q$ lines, $i$-th line should contain answer for a board after $i$ queries of Ildar. This line should contain "YES" if it is possible to place the kings on the available cells in the desired way, or "NO" otherwise.

输出 $q$ 行，第 $i$ 行应包含在执行 Ildar 的前 $i$ 个查询后对应棋盘的答案。若能在可用格子上按要求放置国王，则该行输出 "YES"；否则输出 "NO"。

In the first example case after the second query only cells $(1, 1)$ and $(1, 5)$ are unavailable. Then Ivan can place three kings on cells $(2, 2)$, $(2, 4)$ and $(2, 6)$.

After the third query three cells $(1, 1)$, $(1, 5)$ and $(2, 4)$ are unavailable, so there remain only 3 available cells: $(2, 2)$, $(1, 3)$ and $(2, 6)$. Ivan can not put 3 kings on those cells, because kings on cells $(2, 2)$ and $(1, 3)$ attack each other, since these cells share a corner.

在第一个样例中，第二次查询后，仅有单元格 $(1, 1)$ 和 $(1, 5)$ 不可用。此时 Ivan 可以在单元格 $(2, 2)$、$(2, 4)$ 和 $(2, 6)$ 上各放置一个国王。

第三次查询后，三个单元格 $(1, 1)$、$(1, 5)$ 和 $(2, 4)$ 不可用，因此仅剩 3 个可用单元格：$(2, 2)$、$(1, 3)$ 和 $(2, 6)$。Ivan 无法在这三个单元格上放置 3 个国王，因为位于 $(2, 2)$ 和 $(1, 3)$ 的国王会互相攻击（这两个单元格共享一个角）。