CF1980F1.Field Division (easy version)

这是该问题的简单版本；它与困难版本的区别仅在于问题本身。简单版本只需要你判断某些值是否为非零。困难版本则需要你输出确切的数值。

Alice 和 Bob 正在分割一块田地。这块田地是一个 $n \times m$ 的矩形（$2 \le n, m \le 10^9$），行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。第 $r$ 行第 $c$ 列的格子记为 $(r, c)$。

Bob 有 $k$ 个喷泉（$2 \le k \le 2 \cdot 10^5$），它们都位于田地中不同的格子里。Alice 负责分割田地，但她必须满足以下几个条件：

• 分割田地时，Alice 会从田地左侧或上侧的任意一个没有喷泉的格子出发，每次只能向下或向右移动到相邻的格子。她的路径将在田地的右侧或下侧结束。
• Alice 的路径会将田地分成两部分——一部分归 Alice 所有（包括她路径上的所有格子），另一部分归 Bob 所有。
• Alice 拥有包含格子 $(n, 1)$ 的那一部分。
• Bob 拥有包含格子 $(1, m)$ 的那一部分。

Alice 希望分割田地，使她获得尽可能多的格子。

Bob 希望保留所有喷泉的所有权，但他可以把其中一个喷泉让给 Alice。首先，输出整数 $\alpha$——如果 Bob 不让出任何喷泉（即所有喷泉都归 Bob 所有），Alice 所能获得的最大田地面积。然后输出 $k$ 个非负整数 $a_1, a_2, \dots, a_k$，其中：

• 如果 Bob 把第 $i$ 个喷泉让给 Alice 后，Alice 所能获得的最大田地面积没有增加（即仍为 $\alpha$），则 $a_i=0$；
• 如果 Bob 把第 $i$ 个喷泉让给 Alice 后，Alice 所能获得的最大田地面积增加了（即大于 $\alpha$），则 $a_i=1$。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n, m \le 10^9$，$2 \le k \le 2 \cdot 10^5$），表示田地的大小和喷泉的数量。

接下来有 $k$ 行，每行包含两个整数 $r_i$ 和 $c_i$（$1 \le r_i \le n$，$1 \le c_i \le m$），表示第 $i$ 个喷泉所在格子的坐标。保证所有格子互不相同，且没有喷泉位于 $(n, 1)$。

保证所有测试用例中 $k$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，首先输出 $\alpha$——如果 Bob 不让出任何喷泉，Alice 所能获得的最大田地面积。然后输出 $k$ 个非负整数 $a_1, a_2, \dots, a_k$，其中：

• 如果 Bob 把第 $i$ 个喷泉让给 Alice 后，Alice 所能获得的最大田地面积没有增加（与所有喷泉都归 Bob 时相同），则 $a_i=0$；
• 如果 Bob 把第 $i$ 个喷泉让给 Alice 后，Alice 所能获得的最大田地面积增加了（比所有喷泉都归 Bob 时更大），则 $a_i=1$。

如果你输出 $1$ 以外的其他正整数，只要它能被 64 位有符号整数类型表示，也会被判为 $1$。因此，困难版本的解法也能通过本题的测试。

以下是第二个样例的图片说明：

喷泉的编号用绿色标注。属于 Alice 的格子用蓝色标记。注意，如果 Bob 把喷泉 $1$ 或喷泉 $3$ 让给 Alice，那么该喷泉不能出现在 Alice 的田地里。

由 ChatGPT 4.1 翻译