#1525. 2529. [Poi2011]Sticks

2529. [Poi2011]Sticks

#2529. [Poi2011]Sticks

题目描述

Little Johnny was given a birthday present by his grandparents. This present is a box of sticks of various lengths and colours. Johnny wonders if there are three sticks in the set he has been given that would form a triangle with different-coloured sides. Let us note that Johnny is interested in non- degenerate triangles only, i.e., those with positive area.

给出若干木棍,每根木棍有特定的颜色和长度。问能否找到三条颜色不同的木棍构成一个三角形。
(注意这里所说的三角形面积要严格大于0)

第一行给出一个整数k(3<=k<=50),表示颜色的种数。这k种颜色被标号为1至k。
接下来k行,第i+1描述颜色为i的木棍的信息。
首先一个整数Ni(1<=Ni<=10^6)表示颜色为i的木棍的数量。
接下来Ni个整数,表示这Ni根木棍各自的长度。
所有木棍的长度<=10^9。总木棍数量<=10^6。

你的程序应该仅输出一行
如果有解,输出6个整数,分别表示第一条边的颜色,第一条边的长度,第二条边的颜色,第二条边的长度,第三条边的颜色,第三条边的长度,这六个整数以空格分割。
如果有多组解,随便输出一组即可。
如果无解,输出 NIE

输入格式

In the first line of the standard input an integer k(3<=k<=50)is given, which is the number of different colours of sticks. The colours themselves are numbered from 1 to k.

The following klines contain descriptions of the sticks of particular colours. The line no. i+1holds integers that describe the sticks of colour , separated by single spaces. The first of these numbers, Ni(1<=Ni<=10^6) denotes the number of sticks of colour . It is followed, in the same line, by Niintegers denoting the lengths of the sticks of colour . All lengths are positive and do not exceed10^9. Furthermore, the total number of all sticks does not exceed 10^6.0020

In tests worth at least 30% of the points the following holds in addition: the total number of the sticks does not exceed 250.

输出格式

Your program should print (on the first and only line of the standard output) either:

  •    six integers, separated by single spaces, that describe the construction of a triangle with different-coloured sides as follows: the colour and the length of the first stick, the colour and the length of the second stick, and the colour and the length of the third stick, 
    
  •    or the word NIE (Polish for _no_ ) if no such triple of sticks exists. 
    

If there are multiple triples of different-coloured sticks that give rise to a triangle, your program may pick one such triple arbitrarily.

样例

样例输入

4  

1 42  

2 6 9  

3 8 4 8  

1 12  

样例输出

3 8 4 12 2 9  

数据范围与提示