8650번 - Konduktorzy 다국어

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 n przedziałów w pociągu jest numerowane liczbami od 1 do n. Podobnie każdy z k konduktorów otrzymuje unikalny identyfikator będący liczbą z przedziału od 1 do k.
• 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.

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite n i k (1 ≤ n ≤ 2·10¹³, 1 ≤ k ≤ 100 000, k ≤ n), oznaczające odpowiednio liczbę przedziałów oraz liczbę konduktorów.

W drugim wierszu znajduje się k parami różnych liczb całkowitych a₁, ..., a_k. Liczba a_i (1 ≤ a_i ≤ 10⁵) oznacza czas sprawdzenia pojedynczego przedziału przez konduktora o identyfikatorze i.

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

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.