[IOI2018] seats 排座位

本题为交互题，但在此请提交**完整程序**。

你要在一个长方形大厅里举办国际编程比赛，该大厅共有 $HW$ 个座位（$H$ 行 $W$ 列）。行的编号是从 $0$ 到 $H-1$，列的编号是从 $0$ 到 $W-1$。位于 $r$ 行 $c$ 列的座位用 $(r,c)$ 表示。一共邀请了 $HW$ 位参赛者，编号是从 $0$ 到 $HW-1$。你制定好了一个座位表，第 $i(0 \leq i \leq HW - 1)$ 个参赛者被安排到座位 $(R_i,C_i)$。座位表中参赛者和座位是一一对应的。 大厅中一个座位集合 $S$ 被称为是**长方形的**，如果存在整数 $r_1, r_2, c_1$ 和 $c_2$ 满足下列条件： - $0 \leq r_1 \leq r_2 \leq H - 1$。 - $0 \leq c_1 \leq c_2 \leq W - 1$。 - $S$ 正好是所有满足 $r_1 \leq r \leq r_2$ 和 $c_1 \leq c \leq c_2$ 的座位 $(r, c)$ 的集合。 如果一个长方形座位集合包含 $k(1 \leq k \leq HW)$ 个座位，并且被分配到这个集合的参赛者的编号恰好是从 $0$ 到 $k-1$，那么该集合是**美妙的**。一个座位表的**美妙度**定义为这个表中美妙的长方形座位集合的个数。 在准备好座位表后，你会收到一些交换两个参赛者座位的请求。具体来说，有 $Q$ 个这样的请求，按时间顺序编号为 $0$ 到 $Q-1$。第 $j(0 \leq j \leq Q - 1)$ 个请求希望交换参赛者 $A_j$ 和 $B_j$ 的座位。你立即接受每个请求并更新座位表。每次更新后，你的目标是计算当前座位表的美妙度。

输入的第一行包含三个正整数 $H, W, Q$，其意义见题目描述。 接下来 $HW$ 行，每行包含两个非负整数。在这 $HW$ 行中，第 $i$ 行的两个整数分别表示 $R_{i - 1}, C_{i - 1}$，即编号为 $i - 1$ 的参赛者初始座位的行和列。 接下来 $Q$ 行，每行包含两个非负整数。在这 $Q$ 行中，第 $j$ 行的两个整数分别表示 $A_{j - 1}, B_{j - 1}$，即在编号为 $j - 1$ 的请求中希望被交换座位的两位参赛者的编号。

输出共 $Q$ 行，每行包含一个整数，第 $i$ 行的整数表示按时间顺序处理完编号为 $i - 1$ 的交换请求之后当前座位表的美妙度。

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

3
4

1 5 3
0 0
0 1
0 2
0 3
0 4
0 1
0 3
4 0

5
3
2

**限制条件** - $1 \leq H$ - $1 \leq W$ - $HW \leq 1, 000, 000$ - $0 \leq R_i \leq H - 1(0 \leq i \leq HW - 1)$ - $0 \leq C_i \leq W - 1(0 \leq i \leq HW - 1)$ - $(R_i, C_i) \neq (R_j, C_j)(0 \leq i < j \leq HW - 1)$ - $1 \leq Q \leq 50, 000$ - $0 \leq A_j \leq HW - 1(0 \leq j \leq Q - 1)$ - $0 \leq B_j \leq HW - 1(0 \leq j \leq Q - 1)$ - $A_j \neq B_j(0 \leq j \leq Q - 1)$ **子任务** - 1.（5 分） $HW \leq 100$，$Q \leq 5, 000$ - 2.（6 分） $HW \leq 10, 000$，$Q \leq 5, 000$ - 3.（20 分） $H \leq 1, 000$，$W \leq 1, 000$，$Q \leq 5, 000$ - 4.（6 分） $Q \leq 5, 000$，$|A_j - B_j| \leq 10, 000(0 \leq j \leq Q - 1)$ - 5.（33 分） $H = 1$ - 6.（30 分） 无附加限制条件