题目描述

Long ago, an alien civilization built a giant monument. The floor of the monument looked like this:

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

Each '#' represents a red tile, and each '.' represents a blue tile. The pattern went on for miles and miles (you may, for the purposes of the problem, assume it was infinite). Today, only a few of the tiles remain. The rest have been damaged by methane rain and dust storms. Given the locations and colours of the remaining tiles, can you find the center of the pattern?

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each one starts with a line containing $N$, the number of remaining tiles. The next $N$ lines each contain $X_i$, $Y_i$, and the tile colour (either '#' or '.').

输出格式

For each test case, output one line containing "Case #$c$: $X$ $Y$", where $c$ is the case number (starting from 1) and ($X$, $Y$) is the location of the center of the pattern. If there is more than one possible answer, output the ($X$, $Y$) closest to (0, 0) in Manhattan distance (the distance in $x$, plus the distance in $y$). If there are still ties, output the one with the largest $X$. If there are still ties after that, output the one with the largest $Y$. If there is no possible answer, output "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

提示

Limits

• $1 \leq T \leq 50.$
• The list of coordinates in each test case will not contain duplicates.

Test set 1 (12 Pts, Visible Verdict)

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

Test set 2 (33 Pts, Hidden Verdict)

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