Problem description

Zbiór dodatnich liczb naturalnych nazywamy antyarytmetycznym, jeżeli nie można w nim wybrać trzech liczb, które tworzą ciąg arytmetyczny (o równej różnicy między dwoma sąsiednimi elementami). Na przykład zbiór {1, 2, 10, 35} jest antyarytmetyczny, natomiast zbiór {3, 5, 8, 10, 11, 30} nie jest (bo można wybrać z niego elementy 5, 8, 11, które tworzą ciąg arytmetyczny o różnicy 3).

Twoim zadaniem jest wygenerować stosunkowo duży zbiór antyarytmetyczny o stosunkowo małych elementach.

Napisz program, który wczyta liczbę N, wyznaczy jakiś zbiór antyarytmetyczny składający się z N (parami różnych) elementów nie przekraczających 1 000 000 i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się jedna liczba naturalna N, oznaczająca oczekiwany rozmiar zbioru antyarytmetycznego.

Wyjście

Twój program powinien wypisać na wyjście dokładnie N parami różnych liczb naturalnych A_i pooddzielanych pojedynczymi odstępami – elementy zbioru antyarytmetycznego.

Wszystkie wypisane liczby muszą spełniać warunek 1 ≤ A_i ≤ 1 000 000.

Jeżeli istnieje wiele możliwych rozwiązań, Twój program może wypisać dowolne z nich. Jeżeli rozwiązanie nie istnieje, zamiast tego należy wypisać tylko jedno słowo NIE.

Ograniczenia

1 ≤ N ≤ 8 000.

Przykład

6

1 10 12 27 28 90