Odbudowa Bajtocji

Limit pamięci: 32 MB

Wszystkie ręce do pracy! Trzeba odbudować Bajtocję po wyniszczającej wojnie!

Tobie przypadł w udziale zaszczyt przypisania kodów pocztowych bajtockim miastom. Każde miasto powinno dostać jeden kod pocztowy, będący liczbą całkowitą dodatnią nie większą niż . Różne miasta powinny mieć różne kody pocztowe.

Poczta bajtocka jest dość dziwnie zorganizowana; aby przesyłka mogła dotrzeć z miasta do miasta , kody pocztowe tych dwóch miast muszą mieć wspólny dzielnik większy niż . Oczywiście chcesz, aby w odbudowanej ojczyźnie można było wysyłać paczki bezpośrednio pomiędzy każdą parą miast.

Dodatkowo, nowa ustawa antykorupcyjna nakłada na Ciebie obowiązek, aby dla każdego zbioru miast Bajtocji, zawierającego więcej niż połowę wszystkich miast, kody pocztowe przypisane miastom z tego zbioru nie miały wspólnego dzielnika większego niż jeden.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia liczbę miast w Bajtocji,
• wyznaczy sposób przypisania miastom w Bajtocji kodów pocztowych,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym i jedynym wierszu wejścia znajduje się jedna liczba całkowita () oznaczająca liczbę miast w Bajtocji.

Wyjście

Należy wypisać dokładnie wierszy. W -tym wierszu powinna się znajdować jedna liczba całkowita dodatnia nie większa niż - zaproponowany kod pocztowy dla -tego miasta Bajtocji. Możesz założyć, że dla każdych możliwych danych wejściowych będzie istniało rozwiązanie. Jeśli istnieje wiele różnych rozwiązań, Twój program powinien wypisać dowolne z nich.

Przykład

Dla danych wejściowych:

5

poprawną odpowiedzią jest:

714
2090
4485
29029
215441

Autor zadania: Marcin Pilipczuk.