追星族

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

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

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

第一行一个整数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)$，描述一场演出的地点与时间。数据中存在演出时间相同或者演出地点相同的数据。

对于每组数据，输出两行：

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

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

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

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

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