Description

外星人已经降临地球。他们对地球上的河流感到非常着迷，因为他们的母星上完全没有流动的水。如今，他们想在地球的某些河流中建造外星建筑。

你的任务是确保这些建筑不会过度阻碍河流的流动，否则将会造成严重后果。特别地，你需要判断在建筑布置完成之后，该河流仍然能够承受的最大水流量。

这些外星人倾向于在笔直且宽度一致的河道段落上建造建筑。因此，你决定将河流建模为一个矩形网格，网格中的每个单元格都有整数坐标 $(X, Y)$，其中 $0 \leq X < W$ 且 $0 \leq Y < H$。每个单元格最多只能承载 $1$ 单位的水流，水只能在边相邻的格子之间流动。

所有在河流南侧（即 $y$ 坐标为 $0$）的格子默认拥有 $1$ 单位的入流量。

建筑均为矩形，且与网格对齐。位于建筑下方的单元格将无法承载任何水流。给定这些限制条件，请你计算出最多有多少单位的水流可以到达河流的北侧（即 $y$ 坐标为 $H - 1$ 的格子）。

Input Format

输入的第一行是测试用例数量 $T$。接下来是 $T$ 个测试用例。

每个测试用例第一行包含三个整数：河流的宽度 $W$，高度 $H$，以及要在河流中建造的建筑数量 $B$。

接下来的 $B$ 行中，每行包含四个整数：$X_0$、$Y_0$、$X_1$ 和 $Y_1$，表示建筑的左下角坐标为 $(X_0, Y_0)$，右上角坐标为 $(X_1, Y_1)$。

建筑之间不会重叠，但可以共边相接。

Output Format

对于每个测试用例，输出一行，格式为 "Case #x: m"，其中 $x$ 是测试用例编号（从 1 开始），$m$ 是该河流中最多可以通过的水流量。

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

Case #1: 1
Case #2: 2

Hint

样例解释

以下是两个样例中河流与建筑布置的可视化图示：

限制条件

• $1 \leq T \leq 100$
• $0 \leq X_0 \leq X_1 < W$
• $0 \leq Y_0 \leq Y_1 < H$

Small 数据集（10 分）

• 时间限制：60 3 秒
• $3 \leq W \leq 100$
• $3 \leq H \leq 500$
• $0 \leq B \leq 10$

Large 数据集（20 分）

• 时间限制：120 5 秒
• $3 \leq W \leq 1000$
• $3 \leq H \leq 10^8$
• $0 \leq B \leq 1000$

翻译由 ChatGPT-4o 完成