Sticks Batch 컴파일 명령

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.

Input

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

The following $k$ lines contain descriptions of the sticks of particular colours. The line no. $i+1$ holds integers that describe the sticks of colour $i$, separated by single spaces. The first of these numbers, $n_i$ ($1 \le n_i \le 1\,000\,000$), denotes the number of sticks of colour $i$. It is followed, in the same line, by $n_i$ integers denoting the lengths of the sticks of colour $i$. All lengths are positive and do not exceed $1\,000\,000\,000$. Furthermore, the total number of all sticks does not exceed $1\,000\,000$.

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

Output

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.

Example

For the input data:

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

the correct result is:

3 8 4 12 2 9

whereas for the input data:

3
1 1
1 2
1 3

the correct result is:

NIE

Task author: Michal Pilipczuk.