Konduktorzy [B]

Limit pamięci: 128 MB

Bajtazar pracuje jako konduktor w Bajtockich Kolejach Państwowych (BKP), które są znane z najdłuższych pociągów osobowych w całej Bajtlandii. Specjalne pociągi wymagają specjalnych rozwiązań, dlatego zarząd BKP wprowadził przepisy mające usprawnić pracę konduktorów. Mówią one między innymi, że sprawdzanie biletów przebiega w następujący sposób:

• Na początku wszystkie przedziałów w pociągu jest numerowane liczbami od do . Podobnie każdy z konduktorów otrzymuje unikalny identyfikator będący liczbą z przedziału od do .
• Następnie każdy z konduktorów rozpoczyna sprawdzanie biletów w przedziale o numerze równym jego identyfikatorowi.
• Konduktor, który sprawdzi bilety w swoim przedziale, rozpoczyna sprawdzanie biletów w przedziale o najmniejszym numerze spośród tych przedziałów, które zostały jeszcze do sprawdzenia. Przy tym, jeśli dwóch konduktorów skończy sprawdzać bilety w tym samym czasie, wówczas pierwszeństwo ma konduktor o mniejszym identyfikatorze.
• Jeśli konduktor skończył sprawdzanie biletów w przedziale i nie ma już przedziałów do sprawdzania, wówczas jego praca została zakończona.
• Sprawdzanie biletów w pociągu zostaje zakończone, gdy we wszystkich przedziałach zostały już sprawdzone bilety.

Ze względów ekonomicznych liczba konduktorów nigdy nie przekracza liczby przedziałów w pociągu.

Wszystkie przedziały w pociągach BKP są identyczne, przez co czas sprawdzania pojedynczego przedziału zależy jedynie od zwinności konduktora. Ponadto, BKP bardzo ceni sobie oryginalność swoich pracowników, dlatego nie ma dwóch konduktorów, którzy sprawdzaliby przedział w takim samym czasie.

Po sprawdzeniu biletów w pociągu, koledzy Bajtazara zawsze przechwalają się, który z nich sprawdził przedział o większym numerze. Pomóż Bajtazarowi stwierdzić, czy ma się czym chwalić, i napisz program, który dla każdego konduktora wyznaczy numer ostatniego przedziału, w którym sprawdził bilety.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i (, , ), oznaczające odpowiednio liczbę przedziałów oraz liczbę konduktorów.

W drugim wierszu znajduje się parami różnych liczb całkowitych . Liczba () oznacza czas sprawdzenia pojedynczego przedziału przez konduktora o identyfikatorze .

Wyjście

W pierwszym wierszu wyjścia Twój program powinien wypisać liczb całkowitych, będących numerami ostatnich przedziałów, jakie sprawdzą konduktorzy (w kolejności rosnących identyfikatorów).

Przykład

Dla danych wejściowych:

10 3
3 5 6

poprawną odpowiedzią jest:

10 9 7

Wyjaśnienie do przykładu: Powyższy obrazek przedstawia przebieg kontroli biletów. Kolumny odpowiadają kolejnym jednostkom czasu, wiersze - konduktorom, a pogrubione liczby - numerom przedziałów, w których znajdują się konduktorzy w danym czasie.

Autor zadania: Bartłomiej Gajewski.