继去年成功建造了一堵无限长的墙之后，Bob 又受聘从事一项新工作。他的首要任务是在一个新的建筑工地上安装多台起重机。

每台起重机由一个中央塔架和一个水平横梁（吊臂）组成，吊臂安装在塔架顶部，可以绕着中央塔架自由旋转。塔架已经安装完毕，位于固定的坐标处，且具有固定的高度。现在只需要安装吊臂。然而，Bob 必须小心谨慎。首先，吊臂的长度不能超过其塔架的高度，否则起重机会直接倾倒。其次，吊臂的长度必须是正整数（单位：米）。第三，任何两台起重机都不应发生碰撞。幸运的是，所有塔架的高度各不相同。因此，两台起重机发生碰撞的唯一方式是其中一台的吊臂撞到了另一台的塔架。注意，吊臂接触到另一台起重机的塔架并不会导致碰撞。

图 J.1：样例 3 的示意图。每个圆圈中心的数字表示该位置起重机的高度。每个箭头上的数字表示该起重机吊臂的长度。

考虑到这一点，Bob 希望最大化至少一台起重机所能覆盖的区域，即地面上那些至少可以被其中一个吊臂通过旋转覆盖到的点的集合。每台起重机的吊臂长度应该设为多少，才能使 Bob 覆盖的区域最大？

输入格式

输入包含： 一行一个整数 $n$ ($1 \le n \le 500$)，表示起重机的数量。 $n$ 行，每行三个整数 $x, y$ 和 $h$ ($0 \le x, y \le 10\,000, 1 \le h \le 10\,000$)，描述起重机的位置及其高度（单位：米）。

保证没有两台起重机位于同一位置，且所有高度各不相同。

输出格式

对于每台起重机，输出其吊臂的正整数长度（单位：米），使得覆盖区域最大。

如果存在多个最优解，输出其中任意一个即可。

样例

样例输入 1

3
1 1 4
4 1 5
7 4 3

样例输出 1

3
5
3

样例输入 2

3
0 0 10
4 6 8
6 6 6

样例输出 2

10
7
1

样例输入 3

5
2 6 2
4 10 4
5 6 6
8 8 7
10 2 8

样例输出 3

2
4
2
6
8