Psst... Ruszyły zawody olimpiady informatycznej dla uczniów szkół podstawowych i średnich. Zadania na tych konkursach są bardzo podobne do zadań, które rozwiązujesz, tutaj, na Szkopule.
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/

Zadanie Odbudowa Bajtocji (odb)

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:

poprawną odpowiedzią jest:

Autor zadania: Marcin Pilipczuk.