Xeno-archaeology (Large)

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

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

Each # is a red tile and each . is a blue tile. The block above is a 15 by 15 window of that floor, and the middle tile of the block sits at the center of the pattern. The pattern keeps the same rule in every direction, so treat the floor as infinite.

Today only a few tiles are left. Methane rain and dust storms destroyed the rest. Every tile sits at integer coordinates. Given the position and the color of each remaining tile, find the center of the pattern.

The first line has one integer $T$, the number of test cases. Each test case starts with a line holding $N$, the number of remaining tiles. Each of the next $N$ lines holds $X_i$, $Y_i$ and the color of that tile, separated by spaces. The color is either # or ..

Limits

• $1 \le T \le 50$
• $1 \le N \le 1000$
• $-10^{15} \le X_i \le 10^{15}$
• $-10^{15} \le Y_i \le 10^{15}$
• The coordinates inside one test case are all different.

For each test case print one line Case #c: X Y, where c is the case number starting from 1 and $(X, Y)$ is the center of the pattern. If several centers explain the remaining tiles, print the one closest to $(0, 0)$ in Manhattan distance, which is the distance in x plus the distance in y. If several centers are still tied, print the one with the largest $X$. If that is still a tie, print the one with the largest $Y$. If no center explains the tiles, print Case #c: Too damaged instead.