Wstęp do algorymów
Problem Flawiusza
Josef ben Matatia (c. 37 – c. 100) („ben” po hebrajsku oznacza „syn”) był żydowskim historykiem. Brał on udział w pierwszej wojnie żydowsko–rzymskiej (66 – 67), gdzie dowodził siłami żydowskimi w Galilei. Poddał się armii rzymskiej dowodzonej przez Wespazjana po sześciotygodniowym oblężeniu Jodfat. Z oblężeniem Jodfatu wiąże się ciekawa historia. Powstańcy woleli umrzeć niż zostać wzięci do rzymskiej niewoli. Jednak religia zabraniała odbierania sobie samemu życia. Z tego powodu żołnierze ustawili się w okrąg i postanowili, poczynając od pierwszego, zabijać co trzeciego towarzysza. Kiedy zostało tylko dwóch wojów – ben Matatia i drugi mężczyzna, Josef przekonał towarzysza aby nie pozbawiać się życia, ale oddać się w ręce wroga. Okazało się to dobrym posunięciem, gdyż po dwóch latach niewoli u Wespazjana, kiedy w 69 r. Wespazjan został cesarzem, Josef został uwolniony i przyjął rzymskie nazwisko Flawiusz.
Pierwszym, który historię Flawiusza przekształcił w problem matematyczny miał być francuski matematyk Claude Gaspar Bachet de Méziriac (1581 – 1638).
Pytanie jest więc następujące. Na okręgu ustawiamy $n$ obiektów. Obiekty numerujemy kolejnymi liczbami naturalnymi od $1$ do $n$. W pierwszym kroku pomijamy pierwszych $k$ obiektów i eliminujemy obiekt o numerze $k+1$. Dalej pomijamy kolejne $k$ obiektów itd. Należy wskazać obiekt, który pozostanie ostatni. Dla $k = 1$ istnieje wzór jawny, jednak problem dla większych $k$ pozostaje otwarty.
Zadanie
W tym problemie prosimy Cię o coś więcej. Masz wskazać kolejne obiekty, które są kolejno eliminowane.
Wejście
Pierwszy i jedyny wiersz wejścia zawiera dwie liczby: $n$ i $k$.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać ciąg liczb – numer kolejno eliminowanych obiektów.
Ograniczenia
- $1\leq n \leq 2\cdot 10^5$
- $0\leq k \leq 100$
Przykłady
Wejście 1
7 2
Wyjście 1
3 6 2 7 5 1 4
Wejście 2
7 0
Wyjście 2
1 2 3 4 5 6 7
Wejście 3
3 5
Wyjście 3
3 2 1