외계 고고학

오래전, 외계 문명이 거대한 기념물을 세웠다. 기념물의 바닥은 다음과 같은 모습이었다.

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

각 '#'은 빨간색 타일을 나타내고, 각 '.'은 파란색 타일을 나타낸다. 이 무늬는 수없이 먼 거리까지 이어졌다(이 문제에서는 무한하다고 가정해도 된다). 오늘날에는 타일 중 몇 개만 남아 있다. 나머지는 메테인 비와 먼지 폭풍으로 손상되었다. 남아 있는 타일의 위치와 색상이 주어질 때, 무늬의 중심을 찾을 수 있는가?

제한

메모리 제한: 1GB. 시간 제한: 테스트 세트당 30초. 1 ≤ T ≤ 50. 각 테스트 케이스의 좌표 목록에는 중복이 없다.

테스트 세트 1 (결과 공개)

1 ≤ N ≤ 100. -100 ≤ $X_{i}$ ≤ 100. -100 ≤ $Y_{i}$ ≤ 100.

테스트 세트 2 (결과 비공개)

1 ≤ N ≤ 1000. -$10^{15}$ ≤ $X_{i}$ ≤ $10^{15}$. -$10^{15}$ ≤ $Y_{i}$ ≤ $10^{15}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 남아 있는 타일의 수 N을 포함하는 한 줄로 시작한다. 다음 N개의 줄에는 각각 $X_{i}$, $Y_{i}$, 그리고 타일의 색상('#' 또는 '.')이 주어진다.

각 테스트 케이스마다 "Case #c: X Y"을 포함하는 한 줄을 출력한다. 여기서 c는 1부터 시작하는 케이스 번호이고, (X, Y)는 무늬 중심의 위치이다. 가능한 답이 둘 이상이면 맨해튼 거리(x 방향 거리와 y 방향 거리의 합)로 (0, 0)에 가장 가까운 (X, Y)를 출력한다. 그래도 동률이면 X가 가장 큰 것을 출력한다. 그 후에도 동률이면 Y가 가장 큰 것을 출력한다. 가능한 답이 없으면 "Case #c: Too damaged"을 출력한다.