Tester wioseł

Limit pamięci: 512 MB

Słowocka firma WKD (Wiosła Kardynalnie Dobre) wyprodukowała nowych rodzajów wioseł! Firma nie posiada dobrej metody mierzenia siły nośnej swoich produktów, więc zatrudniła profesjonalnego testera wioseł, Słowomira. Niestety, jego sposób określania siły nośnej wioseł również nie jest zbyt dokładny - bierze on każdą możliwą parę wioseł, wsiada do łódki i przepływa do boi i nazad. Następnie zapisuje on: Jestem pewien, że sumaryczna siła wioseł nie przekraczała , ale jedno z nich na pewno miało siłę co najmniej , bo ręka mi się zmęczyła. Po zakończeniu testów Słowomir przekazał wyniki Mirosłowie, szefowej WKD. Uważa ona jednak, że danych jest za dużo, a w dodatku są mało znaczące. Wolałaby ona znać dowolny ciąg wartości sił nośnych, który zgadzałby się z wynikami testera. Podaj taki ciąg.

Wejście

W pierwszym wierszu wejścia znajduje się liczba całkowita (), oznaczająca liczbę rodzajów wioseł. Rodzaje wioseł numerujemy liczbami od do . W kolejnych wierszach znajduje się po liczb: -ta liczba w -tym wierszu to (), czyli ograniczenie górne na sumaryczną siłę nośną wioseł rodzajów i . Kolejny wiersz jest pusty. Po nim znów następuje wierszy po liczb. Liczba w -tym wierszu na pozycji to (). Oznacza ona, że wiosło rodzaju lub wiosło rodzaju ma siłę nośną co najmniej .

Wyjście

Na wyjście należy wypisać dodatnich liczb całkowitych: -ta liczba ma oznaczać siłę nośną wiosła rodzaju w pewnym ciągu wartości sił nośnych zgodnym z informacjami przekazanymi przez Słowomira. Możesz założyć, że istnieje poprawne rozwiązanie.

Przykład

Dla danych wejściowych:

3
6 8 5
7 6 6
5 7 7

2 3 1
3 1 1
2 1 3

poprawną odpowiedzią jest:

2 3 3