W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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.
In the first line of the standard input an integer () is given, which is the number of different colours of sticks. The colours themselves are numbered from to .
The following lines contain descriptions of the sticks of particular colours. The line no. holds integers that describe the sticks of colour , separated by single spaces. The first of these numbers, (), denotes the number of sticks of colour . It is followed, in the same line, by integers denoting the lengths of the sticks of colour . All lengths are positive and do not exceed . Furthermore, the total number of all sticks does not exceed .
In tests worth at least 30% of the points the following holds in addition: the total number of the sticks does not exceed .
Your program should print (on the first and only line of the standard output) either:
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.