logo AlgoBeat OnlineJudge
登录 注册

#102926. [BZOJ 2926] [Poi1999]空立方体问题

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

如果满足下面条件我们称这个立方体是规则的:

  • 它的顶点中的一个是坐标为 的点;
  • 开始于这个顶点的位于坐标系统的正半轴;
  • 边不长于

有一个给定的空间点的集合 ,坐标为间隔为 的整数。我们试着找出最大体积的规则立方体,它不包括集合 的任何点。如果一个点属于一个立方体之内,那么这个点属于这个立方体,它是这个立方体的点,但它的墙不是。

任务

写一个程序:

  • 读取来自集合 的点的坐标;
  • 找出一个最大体积的规则立方体,它不包括来自集合 的任何点;
  • 把结果输出。

输入格式

首行,一个非零的整数 被写出来。它是集合 的元素数。

接下来的 行中有三个一组的整数,其范围在 ,它们是来自集合 的点的坐标(分别为 )。每一行的数字被单空格号隔开。

输出格式

一行应该有三个被单空格号分隔的整数。这些是最大体积的规则立方体的顶点的坐标(分别为 )。我们要求坐标为正数。

样例

样例输入 #1

4
3 3 300000
2 200000 5
90000 3 2000
2 2 1000

样例输出 #1

1000000 200000 1000

数据范围与提示

对于 的数据,