외계 고고학 (Large)

아주 오래전 어느 외계 문명이 거대한 기념물을 세웠다. 기념물의 바닥은 다음과 같았다.

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

#는 붉은 타일, .는 푸른 타일이다. 위 블록은 그 바닥을 15 x 15 크기로 잘라낸 것이고, 블록의 가운데 타일이 무늬의 중심에 놓인다. 무늬는 사방으로 같은 규칙을 이어가므로 바닥은 무한하다고 본다.

지금은 타일이 몇 장만 남았다. 나머지는 메탄 비와 모래 폭풍에 부서졌다. 타일은 모두 정수 좌표에 놓인다. 남은 타일의 위치와 색이 주어질 때 무늬의 중심을 찾아라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 남은 타일의 수 $N$이 주어진다. 이어지는 $N$개의 줄에는 각각 $X_i$, $Y_i$와 그 타일의 색이 공백으로 구분되어 주어진다. 색은 # 또는 .이다.

제한

• $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}$
• 한 테스트 케이스 안의 좌표는 모두 다르다.

각 테스트 케이스마다 Case #c: X Y 형식으로 한 줄을 출력한다. c는 1부터 시작하는 테스트 케이스 번호이고, $(X, Y)$는 무늬의 중심이다. 남은 타일을 설명하는 중심이 여러 개면 $(0, 0)$에서 맨해튼 거리, 즉 x 방향 거리와 y 방향 거리의 합이 가장 작은 것을 출력한다. 그래도 여러 개면 $X$가 가장 큰 것을 출력하고, 그래도 여러 개면 $Y$가 가장 큰 것을 출력한다. 타일을 설명하는 중심이 없으면 Case #c: Too damaged를 출력한다.