你要在一个长方形大厅里举办国际编程比赛，该大厅共有 $HW$ 个座位（$H$ 行 $W$ 列）。行的编号是从 $0$ 到 $H-1$，列的编号是从 $0$ 到 $W-1$。位于 $r$ 行 $c$ 列的座位用 $(r,c)$ 表示。一共邀请了 $HW$ 位参赛者，编号是从 $0$ 到 $HW-1$。你制定好了一个座位表，第 $i$（$0\le i\le HW-1$）个参赛者被安排到座位 $(R_i,C_i)$。座位表中参赛者和座位是一一对应的。

大厅中一个座位集合 $S$ 被称为是长方形的，如果存在整数 $r_1,r_2,c_1$ 和 $c_2$ 满足下列条件：

• $0\le r_1\le r_2\le H-1$。
• $0\le c_1\le c_2\le W-1$。
• $S$ 正好是所有满足 $r_1\le r\le r_2$ 和 $c_1\le c\le c_2$ 的座位 $(r,c)$ 的集合。

如果一个长方形座位集合包含 $k$（$1\le k\le HW$）个座位，并且被分配到这个集合的参赛者的编号恰好是从 $0$ 到 $k-1$，那么该集合是美妙的。一个座位表的美妙度定义为这个表中美妙的长方形座位集合的个数。

在准备好座位表后，你会收到一些交换两个参赛者座位的请求。具体来说，有 $Q$ 个这样的请求，按时间顺序编号为 $0$ 到 $Q-1$。第 $j$（$0\le j\le Q-1$）个请求希望交换参赛者 $A_j$ 和 $B_j$ 的座位。你立即接受每个请求并更新座位表。每次更新后，你的目标是计算当前座位表的美妙度。

实现细节

你应该实现下列过程和函数：

give_initial_chart(int H, int W, int[] R, int[] C)

• H, W：行数和列数
• R, C：两个长度为 $HW$ 的数组，代表初始的座位表
• 这个过程只被调用一次，而且是在 swap_seats 的任何调用之前。

int swap_seats(int a, int b)

• 该函数用来处理一次交换座位的请求
• a, b：需要交换座位的参赛者
• 该函数被调用 $Q$ 次
• 该函数应返回交换座位后座位表的美妙度

例子

令 $H=2$，$W=3$，$R=[0,1,1,0,0,1]$，$C=[0,0,1,1,2,2]$，和 $Q=2$。

评测程序先调用 give_initial_chart(2, 3, [0, 1, 1, 0, 0, 1], [0, 0, 1, 1, 2, 2])。

最初，座位表如下：

\begin{matrix} 0 & 3 & 4 \\ 1 & 2 & 5 \end{matrix}

假设评测程序调用 swap_seats(0, 5)。在这个编号为 $0$ 的请求完成后，座位表变成：

\begin{matrix} 5 & 3 & 4 \\ 1 & 2 & 0 \end{matrix}

对应参赛者集合 $\{0\},\{0,1,2\}$ 和 $\{0,1,2,3,4,5\}$ 的三个座位集合都是长方形和美妙的。所以，该座位表的美妙度为 $3$，swap_seats 应该返回 $3$。

假设评测程序再次调用 swap_seats(0, 5)。在这个编号为 $1$ 的请求完成后，座位表回到初始状态。对应参赛者集合 $\{0\},\{0,1\},\{0,1,2,3\}$ 和 $\{0,1,2,3,4,5\}$ 的四个座位集合都是长方形和美妙的。所以，该表的美妙度为 $4$，swap_seats 应该返回 $4$。

在样例数据下载中的文件ex_seats1.in和ex_seats1.out对应于上述例子。此外，样例数据包中还有一些其他的输入输出例子。

限制条件

• $1\le H$
• $1\le W$
• $HW\le 1\ 000\ 000$
• $0\le R_i\le H-1$（$0\le i\le HW-1$）
• $0\le C_i\le W-1$（$0\le i\le HW-1$）
• $(R_i,C_i)\ne(R_j,C_j)$（$0\le i<j\le HW-1$）
• $1\le Q\le 50\ 000$
• 对于 swap_seats 的所有调用，$0\le a\le HW-1$
• 对于 swap_seats 的所有调用，$0\le b\le HW-1$
• 对于 swap_seats 的所有调用，$a\ne b$

子任务

1. （5分）$HW\le 100$，$Q\le 5\ 000$
2. （6分）$HW\le 10\ 000$，$Q\le 5\ 000$
3. （20分）$H\le 1\ 000$，$W\le 1\ 000$，$Q\le 5\ 000$
4. （6分） 对于 swap_seats 的所有调用，$Q\le 5\ 000$，$|a-b|\le 10\ 000$
5. （33分）$H=1$
6. （30分）无附加限制条件

评测程序示例

评测程序示例按照以下格式读入输入

• 第 $1$ 行：$H\ W\ Q$
• 第 $2+i$ 行（$0\le i\le HW-1$） : $R_i\ C_i$
• 第 $2+HW+j$ 行（$0\le j\le Q-1$）：$A_j\ B_j$

这里 $A_j$ 和 $B_j$ 是调用 swap_seats 处理请求时的参数。

评测程序示例按照以下格式打印你的答案：

• 第 $1+j$ 行（$0\le j\le Q-1$）：swap_seats 对于请求 $j$ 的返回值

约定及限制

对于所支持的各种编程语言，下面列出了对应的数据类型。对于数据类型的细节等，参见实现示例。

时间限制：$3\texttt{s}$

空间限制：$268\texttt{MB}$

下载

样例数据下载