题目描述

Little Sin 住在一个曼哈顿网格状的城市里，这是一个二维平面，人们只能沿着网格向北、西、南或东行走。从 ($x_1$, $y_1$) 到 ($x_2$, $y_2$) 的距离为 $|x_1 - x_2| + |y_1 - y_2|$。

Little Sin 非常喜欢聚会，她希望这个星期天在曼哈顿举办一场家庭聚会。Little Sin 已经收集了一份将要参加聚会的人员名单，现在她需要决定在谁的家里举办聚会。

Little Sin 邀请了若干矩形区域内的所有人，并且所有人都已答应参加。一个矩形区域表示为 ($x_1$, $y_1$, $x_2$, $y_2$)，其中 $x_1 \le x_2$, $y_1 \le y_2$。居住在该矩形区域内的人填满其内部的所有整点。因此，矩形区域 ($x_1$, $y_1$, $x_2$, $y_2$) 内总共有 $(x_2 - x_1 + 1) \times (y_2 - y_1 + 1)$ 个人。

Little Sin 知道这些矩形区域的坐标。她希望聚会能在其中某位参加者的家中举办，但同时也希望其他人不必长途跋涉：她想最小化所有参加者住处到聚会地点的距离总和。你能帮帮她吗？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例以一行包含一个整数 $\mathbf{B}$ 开始，表示矩形区域的个数。紧接着 $\mathbf{B}$ 行，每行包含 $4$ 个整数：$x_1$, $y_1$, $x_2$, $y_2$，表示 Little Sin 邀请参加聚会的一个矩形人群区域的坐标。

输出格式

对于每个测试用例，输出一行内容为 "Case #t: $x$ $y$ $d$"，其中 $t$ 是测试用例编号（从 $1$ 开始），($x$, $y$) 是聚会应当举办在其家中的人的坐标。如果有多个位置的最小总距离相同，选择 $x$ 最小的那个。如果仍有多个位置，选择 $y$ 最小的那个。值 $d$ 是所有参加者住处到点 ($x$, $y$) 的距离总和。

2
1
0 0 2 2
3
-1 2 -1 2
0 0 0 0
1 3 1 3

Case #1: 1 1 12
Case #2: -1 2 6

提示

限制

$1 \le T \le 10$。

$|x_1|, |y_1|, |x_2|, |y_2| \le 10^9$。

$x_1 \le x_2$, $y_1 \le y_2$。

同一个测试用例内的矩形区域互不相交。

测试集 1 - 可见

$1 \le B \le 100$。

每个测试用例中总人数 $\le 1000$。

测试集 2 - 隐藏

$1 \le B \le 1000$。

每个测试用例中总人数 $\le 1000000$。

翻译由 DeepSeek V4 Pro 完成