Patyczki
Limit pamięci: 32 MB
Mały Jaś dostał od babci i dziadka prezent na urodziny.
Jest nim pudełko pełne patyczków różnej długości i różnych kolorów.
Jaś zastanawia się, czy z pewnych trzech patyczków z zestawu da się zbudować
trójkąt o wszystkich bokach różnych kolorów.
Jasia interesują tylko trójkąty niezdegenerowane, czyli takie o dodatnim polu.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita () -
jest to liczba różnych kolorów patyczków.
Kolory numerujemy od do .
W kolejnych wierszach znajdują się opisy patyczków poszczególnych kolorów.
W wierszu o numerze znajdują się liczby całkowite pooddzielane pojedynczymi odstępami, opisujące patyczki koloru .
Pierwsza z tych liczb, (), oznacza liczbę patyczków koloru .
Po niej następuje liczb całkowitych oznaczających długości patyczków.
Są to liczby całkowite dodatnie nie większe niż .
Łączna liczba wszystkich patyczków nie przekracza .
W testach wartych przynajmniej 30% punktów zachodzi dodatkowy warunek: sumaryczna liczba patyczków nie przekracza .
Wyjście
Twój program powinien wypisać (w pierwszym i jedynym wierszu standardowego wyjścia):
-
albo sześć liczb całkowitych pooddzielanych pojedynczymi odstępami, opisujących sposób zbudowania
trójkąta o różnokolorowych bokach w następującym formacie:
kolor i długość pierwszego patyczka, kolor i długość drugiego patyczka oraz kolor i długość trzeciego patyczka,
-
albo słowo NIE, jeżeli takie trzy patyczki nie istnieją.
Jeżeli istnieje wiele trójek patyczków w różnych kolorach, z których można zbudować trójkąt,
Twój program może wypisać dowolną z nich.
Przykład
Dla danych wejściowych:
4
1 42
2 6 9
3 8 4 8
1 12
poprawną odpowiedzią jest:
3 8 4 12 2 9
natomiast dla danych:
3
1 1
1 2
1 3
poprawnym wynikiem jest:
NIE
Autor zadania: Michał Pilipczuk.