Studia [A]

Limit pamięci: 64 MB

Studia na Uniwersytecie Bajtockim (UB) składają się z etapów, które odpowiadają polskim semestrom studiów, tyle że może ich być mniej lub więcej. Każdy student w trakcie nauki na uniwersytecie składa wiele podań do dziekana swojego wydziału, które wpływają na jego przebieg studiów. W szczególności dzięki podaniom studenci mogą zmieniać etapy studiów, na których się aktualnie znajdują. Złożenie podania może mieć także konsekwencje finansowe dla studenta - zarówno korzystne (uzyskanie stypendium), jak i niekorzystne (opłaty za zaliczanie dodatkowych przedmiotów, powtarzanie przedmiotów itd.).

Bajtazar jest leniwym, ale wyjątkowo sprytnym studentem UB. Przez lata zbierał dane o różnych podaniach, jakie składali inni studenci, i dla każdego z nich zapamiętywał, jak wpłynęło ono na aktualny etap studiów składającego go studenta oraz jakie były jego konsekwencje finansowe. Bajtazarowi nie zależy bynajmniej na szybkim zakończeniu studiów, lecz na osiągnięciu jak najwyższych korzyści materialnych. Gwarancję nieograniczonych korzyści daje sytuacja, w której można rozpocząć studia na jakimś etapie, następnie złożyć kolejno pewną liczbę podań tak, aby na sam koniec wrócić na wyjściowy etap studiów i w wyniku całego procesu zarobić dodatnią liczbę bajtalarów. Bajtazar jest bardzo cierpliwy w dążeniu do celu: może sobie pozwolić na złożenie wielu podań, ba, nawet na złożenie tego samego podania wielokrotnie w trakcie całego procesu, o ile tylko wszystko zakończy się upragnionym zyskiem. W swoich planach zakłada on, że dziekan pracuje w sposób deterministyczny, to znaczy że wynik złożenia ustalonego podania z archiwum Bajtazara jest zawsze taki sam.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opisy wszystkich podań, jakie Bajtazar zdołał dotychczas zebrać,
• wyznaczy wszystkie takie numery etapów studiów na UB, które dają gwarancję nieograniczonych korzyści finansowych,
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite oraz (, ), oddzielone pojedynczym odstępem i oznaczające liczbę etapów studiów na UB oraz liczbę podań znajdujących się w archiwum Bajtazara. Kolejne wierszy zawiera po trzy liczby całkowite , oraz (, , ), pooddzielane pojedynczymi odstępami i oznaczające: etap studiów, na którym to podanie zostało złożone przez studenta, etap studiów, na którym znalazł się on w wyniku złożenia podania oraz konsekwencje finansowe, jakie student poniósł (wartość dodatnia oznacza zysk studenta, a ujemna - stratę). Żadna para nie pojawi się na wejściu więcej niż raz, ale pojawić się mogą równocześnie pary i .

Wyjście

Pierwszy wiersz wyjścia powinien zawierać jedną liczbę , oznaczającą liczbę różnych etapów studiów, z których rozpocząwszy studia, Bajtazar może osiągnąć nieograniczone korzyści finansowe. Drugi wiersz powinien zawierać liczb całkowitych ze zbioru , pooddzielanych pojedynczymi odstępami i oznaczających wszystkie takie etapy. Numery etapów powinny być wymienione w kolejności rosnącej.

Przykład

Dla danych wejściowych:

8 8
1 2 3
1 3 -3
5 4 4
6 5 -1
6 7 -1
7 8 5
8 6 2
4 8 -3

poprawną odpowiedzią jest:

5
4 5 6 7 8

Autor zadania: Jakub Radoszewski.