Оператор мобільного зв'язку пропонує таку акцію: кожен новий клієнт може обрати рівно $k$ інших телефонних номерів, і всі дзвінки між клієнтом та будь-яким із $k$ обраних контактів будуть безкоштовними (в обох напрямках).
Група з $n$ студентів (пронумерованих від $1$ до $n$) хоче скористатися цією акцією. Кожен студент $i$ повинен обрати рівно $k$ різних контактів із множини $\{1, 2, \dots, n\} \setminus \{i\}$.
Скажемо, що два студенти $i$ та $j$ можуть розмовляти безкоштовно, якщо виконується принаймні одна з таких умов:
- $i$ обрав $j$ як один із безкоштовних контактів, або
- $j$ обрав $i$ як один із безкоштовних контактів.
Студенти хочуть обрати свої безкоштовні контакти так, щоб будь-який студент міг розмовляти з будь-яким іншим студентом безкоштовно, тобто для кожної пари $(i, j)$, де $1 \le i < j \le n$, студенти $i$ та $j$ могли розмовляти безкоштовно.
Для заданого $k$ ваше завдання:
- визначити максимально можливу кількість студентів $n$, для якої така конфігурація можлива,
- побудувати одну коректну конфігурацію обраних контактів для цього максимального $n$.
Вхідні дані
Вхідні дані складаються з одного цілого числа $k$.
Вихідні дані
У першому рядку виведіть одне ціле число $n$ — максимальну кількість студентів, для якої можливо обрати безкоштовні контакти так, щоб будь-які два студенти могли розмовляти один з одним безкоштовно.
У наступних $n$ рядках виведіть по $k$ безкоштовних контактів, обраних кожним студентом: у рядку $i+1$ (для $1 \le i \le n$) виведіть $k$ різних цілих чисел $a_{i,1}, a_{i,2}, \dots, a_{i,k}$. Кожне $a_{i,j}$ повинно задовольняти умови $1 \le a_{i,j} \le n$ та $a_{i,j} \neq i$. Ці рядки означають, що студент $i$ обрав студентів $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ як свої безкоштовні контакти.
Якщо існує декілька коректних відповідей, виведіть будь-яку з них.
Обмеження
- $1 \le k \le 1000$.
Приклад 1
2
5
2 5
3 4
1 5
1 3
2 4
Примітки
У прикладі $k = 2$, а максимальна кількість студентів, для якої можливо обрати безкоштовні контакти так, щоб будь-які два студенти могли розмовляти один з одним безкоштовно, дорівнює $n = 5$. Для кожної пари різних студентів принаймні один із них обрав іншого, тож будь-які двоє можуть розмовляти безкоштовно.