[AdditionalFile2170.zip](file://AdditionalFile2170.zip?type=additional_file)

#2170. 「POI2011 R3」木棍 Sticks

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

译自 POI 2011 Round 3. Day 2. B「Sticks」

有若干彩色的木棍，求是否存在三根互不同色的木棍，能够构成一个非退化的三角形（即面积为正的三角形）。

输入格式

第一行一个正整数 $k$ 表示颜色种类数。
接下来 $k$ 行，每行若干个空格隔开的正整数，描述木棍。第 $(i+1)$ 行第一个数为 $n_i$，表示颜色 $i$ 的木棍数。该行接下来 $n_i$ 个正整数，描述这种颜色的木棍的长度。

输出格式

• 若不存在，则输出一行NIE；
• 否则，输出一行六个空格隔开的数，分别表示第一根木棍的颜色，第一根木棍的长度，第二根木棍的颜色，第二根木棍的长度，第三根木棍的颜色，以及第三根木棍的长度。

如果有多解，任意输出一个即可。

样例 1

输入

4
1 42
2 6 9
3 8 4 8
1 12

输出

3 8 4 12 2 9

样例 2

输入

3
1 1
1 2
1 3

输出

NIE

数据范围与提示

对于 $30\%$ 的数据，$\sum_{i=1}^kn_i\le 250$。
对于 $100\%$ 的数据，$3\le k\le 50,1\le n_i\le 10^6,\sum_{i=1}^kn_i\le 10^6$，木棍长度$\le 10^9$。

SPJ: ceba (updated by cyand1317) Translated by diamond_duke.