Operator sieci komórkowej oferuje następującą promocję: każdy nowy klient może wybrać dokładnie $k$ innych numerów telefonów, a wszystkie połączenia pomiędzy klientem a dowolnym z $k$ wybranych kontaktów są darmowe (w obu kierunkach).
Grupa $n$ studentów (ponumerowanych od $1$ do $n$) chce skorzystać z tej promocji. Każdy student $i$ musi wybrać dokładnie $k$ różnych kontaktów ze zbioru $\{1, 2, \dots, n\} \setminus \{i\}$.
Mówimy, że dwaj studenci $i$ oraz $j$ mogą rozmawiać za darmo, jeśli zachodzi co najmniej jeden z poniższych warunków:
- $i$ wybrał $j$ jako jeden z darmowych kontaktów, lub
- $j$ wybrał $i$ jako jeden z darmowych kontaktów.
Studenci chcą wybrać swoje darmowe kontakty tak, aby każdy student mógł rozmawiać z każdym innym studentem za darmo, tzn. dla każdej pary $(i, j)$ spełniającej $1 \le i < j \le n$ studenci $i$ oraz $j$ mogą rozmawiać za darmo.
Dla danego $k$ Twoim zadaniem jest:
- wyznaczyć maksymalną możliwą liczbę $n$ studentów, dla której taka konfiguracja jest możliwa,
- skonstruować jedną poprawną konfigurację wybranych kontaktów dla tego maksymalnego $n$.
Wejście
Wejście składa się z jednej liczby całkowitej $k$.
Wyjście
W pierwszym wierszu wypisz jedną liczbę całkowitą $n$ — maksymalną liczbę studentów, dla której możliwe jest wybranie darmowych kontaktów tak, aby dowolnych dwóch studentów mogło rozmawiać ze sobą za darmo.
W kolejnych $n$ wierszach wypisz po $k$ darmowych kontaktów wybranych przez każdego studenta: w wierszu $i+1$ (dla $1 \le i \le n$) wypisz $k$ różnych liczb całkowitych $a_{i,1}, a_{i,2}, \dots, a_{i,k}$. Każde $a_{i,j}$ musi spełniać $1 \le a_{i,j} \le n$ oraz $a_{i,j} \neq i$. Wiersze te oznaczają, że student $i$ wybrał studentów $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ jako swoje darmowe kontakty.
Jeśli istnieje wiele poprawnych odpowiedzi, wypisz dowolną z nich.
Ograniczenia
- $1 \le k \le 1000$.
Przykład 1
2
5
2 5
3 4
1 5
1 3
2 4
Uwagi
W przykładzie $k = 2$, a maksymalna liczba studentów, dla której możliwe jest wybranie darmowych kontaktów tak, aby dowolnych dwóch studentów mogło rozmawiać ze sobą za darmo, wynosi $n = 5$. Dla każdej pary różnych studentów co najmniej jeden z nich wybrał drugiego, więc dowolnych dwóch może rozmawiać za darmo.