Geometria obliczeniowa

Limit pamięci: 64 MB

Bajtazar przygotowuje najtrudniejsze zadanie na ostatnią, zdalną rundę Potyczek Algorytmicznych 2012. Fakt, że problem dotyczy geometrii obliczeniowej, a konkretnie przecinania wielokąta z okręgami, zupełnie nikogo nie zaskakuje.

Jak wiadomo, największą trudnością w geometrii obliczeniowej jest radzenie sobie z rozmaitymi przypadkami szczególnymi. Bajtazar ustalił, że w przygotowywanym przez niego zadaniu najtrudniej jest uporać się z sytuacją, gdy dany wielokąt ma pole równe liczbie jego wierzchołków. Ponadto, taki wielokąt powinien mieć boki równoległe do osi prostokątnego układu współrzędnych i każde dwa kolejne boki wielokąta powinny być prostopadłe. Boki wielokąta nie mogą mieć punktów wspólnych, oprócz wierzchołków wspólnych dla dwóch kolejnych boków wielokąta.

Generowanie takich wielokątów przerosło możliwości Bajtazara, dlatego poprosił Cię o pomoc.

Wejście

W pierwszym i jedynym wierszu wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę wierzchołków szukanego wielokąta.

Wyjście

Jeśli nie da się skonstruować -wierzchołkowego wielokąta spełniającego warunki zadania, należy wypisać słowo NIE . W przeciwnym przypadku na wyjściu należy wypisać dokładnie wierszy. W -tym wierszu powinny znaleźć się dwie liczby całkowite i , oznaczające współrzędne -tego wierzchołka szukanego wielokąta. Wierzchołki powinny być wypisane zgodnie z kolejnością ich występowania na obwodzie wielokąta (kierunek wypisywania wierzchołków wzdłuż obwodu może być dowolny). Wartość bezwzględna liczb wypisanych na wyjściu nie powinna przekraczać .

Przykład

Dla danych wejściowych:

4

poprawną odpowiedzią jest:

0 0
2 0
2 2
0 2

Autor zadania: Jakub Łącki.