Description

很久以前，一个外星文明建造了一座巨大的纪念碑。纪念碑的地板图案如下：

###############
#.............#
#.###########.#
#.#.........#.#
#.#.#######.#.#
#.#.#.....#.#.#
#.#.#.###.#.#.#
#.#.#.#.#.#.#.#
#.#.#.###.#.#.#
#.#.#.....#.#.#
#.#.#######.#.#
#.#.........#.#
#.###########.#
#.............#
###############

每个 # 代表一块红色瓷砖，每个 . 代表一块蓝色瓷砖。这个图案曾经向四面八方无限延展（在本题中，你可以假设它是无限的）。而今天，只剩下少量瓷砖还留存，其他的都被甲烷雨和尘暴损坏了。现给出所有还剩下的瓷砖的位置和颜色，你能否找出这个图案的中心位置？

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组数据第一行为整数 $N$，表示剩余瓷砖的数量。接下来的 $N$ 行，每行包含 $X_i$、$Y_i$ 以及瓷砖颜色（# 或 .）。

Output Format

对于每个测试用例，输出一行 "Case #$c$: $X$ $Y$"，其中 $c$ 为测试用例编号（从 1 开始），($X$, $Y$) 为图案中心的位置。如果有多个可能的答案，输出与 $(0, 0)$ 曼哈顿距离（$|X| + |Y|$）最小的那个。如果仍有多解，输出 $X$ 最大的那个；如果仍有多解，输出 $Y$ 最大的那个。如果无解，输出 "Case #$c$: Too damaged"。

6
1
0 0 .
1
0 0 #
3
0 0 #
0 1 #
1 0 #
5
50 30 #
49 30 #
49 31 #
49 32 #
50 32 #
2
-98 0 #
99 50 .
4
88 88 .
88 89 .
89 88 .
89 89 .

Case #1: 0 0
Case #2: 1 0
Case #3: 1 1
Case #4: 50 31
Case #5: 1 0
Case #6: Too damaged

Hint

限制条件

• $1 \leq T \leq 50$。
• 每组测试数据中的坐标不会重复。

测试集 1（12 分，结果可见）

• $1 \leq N \leq 100$。
• $-100 \leq X_i \leq 100$。
• $-100 \leq Y_i \leq 100$。

测试集 2（33 分，结果隐藏）

• $1 \leq N \leq 1000$。
• $-10^{15} \leq X_i \leq 10^{15}$。
• $-10^{15} \leq Y_i \leq 10^{15}$。

翻译由 ChatGPT-4.1 完成。