Description

在去年的无限墙建设取得成功后，Bob 被雇佣到一个新的工地工作。 他的第一个任务是在新的工地上安装多台起重机。

:::align{center}

Pixabay Content Licence by tonisun on Pixabay

:::

每台起重机由一个中央塔楼和一个水平的横梁（称为“臂架”）组成，臂架安装在塔楼顶部，可以自由地绕塔楼旋转。 塔楼的位置和高度已经为 Bob 安装好了，坐标和高度都是固定的。 现在只需要安装臂架。 不过，Bob 在安装时需要注意以下几点： 首先，臂架的长度不能超过其塔楼的高度，否则起重机会倾倒。 其次，臂架的长度必须是正整数米。 第三，任何两台起重机都不能发生碰撞。 幸运的是，所有塔楼的高度都不相同。 因此，唯一可能发生碰撞的情况是，一台起重机的臂架撞到了另一台起重机的塔楼。 注意，臂架仅仅接触到另一台塔楼并不会导致碰撞。

:::align{center}

图 J.1：样例输入 3 的示意图。每个圆心的数字表示该位置起重机的高度，每个箭头的数字表示该起重机臂架的长度。

:::

在此基础上，Bob 希望最大化至少被一台起重机覆盖到的区域面积，也就是说，最大化通过旋转臂架，至少有一台起重机的臂架可以覆盖到的地面点的面积。 你应该为每台起重机选择多长的臂架，才能使被覆盖的面积最大？

Input Format

输入包含：

• 一行一个整数 $n$（$1\leq n\leq500$），表示起重机的数量。
• 接下来 $n$ 行，每行三个整数 $x$、$y$ 和 $h$（$0\leq x,y\leq 10\,000$，$1\leq h\leq 10\,000$），表示一台起重机的位置和高度，单位为米。

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

Output Format

对于每台起重机，输出其臂架的正整数长度（单位为米），使得被覆盖的面积最大。

如果有多组最优解，输出任意一组均可。

3
1 1 4
4 1 5
7 4 3

3
5
3

3
0 0 10
4 6 8
6 6 6

10
7
1

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

2
4
2
6
8

Hint

由 ChatGPT 4.1 翻译