追星族

Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

度度熊最近迷上了S明星,恰逢她正在巡回演出,得知所有的演出安排后,它希望一场不落的看完所有的演出。

每场演出的地点 $(X_i, Y_i)$ 以及时间$T_i$,这些信息事先都已经公布。但唯一的问题是,单位时间内度度熊的移动速度只有可怜的1。它当然希望离自己的偶像越近越好,所以它希望在所有的演出时刻,它距离演出地点距离的最大值可以最小。度度熊在时间点0时刻出发,并且它可以选择任何一个位置作为起点。

生活在一个格子化的二次元中,度度熊是这样计算距离的:$|x_1 - x_2| + |y_1 - y_2|$

Input

第一行一个整数T,表示T组数据。

每组样例的第一行有一个整数$N (1 \leq N \leq 50 000)$,表示演出的场数。

接下来的N行,每行包括三个整数$X_i, Y_i, T_i (-10^9 \leq X_i, Y_i \leq 10^9, 0 \leq T_i \leq 10^9)$,描述一场演出的地点与时间。数据中存在演出时间相同或者演出地点相同的数据。

Output

对于每组数据,输出两行:

第一行输出:"Case #i:"。i代表第i组测试数据。

第二行输出最小的最大距离。为了尽量精确,用分数A/B的形式表示,其中A和B不可继续化简。

Sample Input

2 2 1 1 2 1 5 1 2 1 1 2 1 5 10

Sample Output

Case #1: 3/2 Case #2: 0/1

Hint

hujie

Source

2015年百度之星程序设计大赛 - 初赛(2)

提交代码