#5256. [Fjwc2018]井井点点

内存限制:256 MiB 时间限制:10 Sec

题目描述

在一个二维平面上有一个图形,如下图所示:
###############
#.............#
#.###########.#
#.#.........#.#
#.#.#######.#.#
#.#.#.....#.#.#
#.#.#.###.#.#.#
#.#.#.#.#.#.#.#
#.#.#.###.#.#.#
#.#.#.....#.#.#
#.#.#######.#.#
#.#.........#.#
#.###########.#
#.............#
###############
它是一个中心为一个字符'.',之后按照一层'#'一层'.'的顺序围起来的无限大的图形。
现在给定若干个位置上的字符,请你确定出这个图形中心位置的坐标,若有多个合法中心位置,
则输出离原点曼哈顿距离最近的一个。若仍有多个,则输出横坐标最大的一个,
若还有多个,输出纵坐标最大的一个;若没有合法中心点,输出"Too damaged".

输入格式

第一行一个正整数T表示数据组数。
对于每组数据,第一行一个正整数n表示已知位置数。
接下来n行,每行两个整数x,y和一个字符c,表示该位置的坐标以及该位置上的字符。
n ≤ 1000, |x|, |y| ≤ 10^15, T ≤ 50 , c ∈ {., #}

输出格式

对于每组数据输出一行表示答案。
格式为:"Case #x: ans",其中x为当前数据的组编号,ans表示答案,#之前有一个空格,:之后有一个空格,
除此之外不允许有任何多余字符。

样例

样例输入


			
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

数据范围与提示