Телефонна компанія

Обмеження: 2 сек., 512 МіБ

Мобільний оператор пропонує таку акцію: кожен новий абонент може вибрати рівно \(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} \ne i\). Ці рядки означають, що студент \(i\) вибрав студентів \(a_{i,1}, a_{i,2}, \dots, a_{i,k}\) як свої безкоштовні контакти.

Якщо існує декілька правильних відповідей, виведіть будь-яку з них.

Обмеження

\(1 \le k \le 1000\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2	5 2 5 3 4 1 5 1 3 2 4

Примітки

У прикладі \(k = 2\), а максимальна кількість студентів, для якої можна вибрати безкоштовні контакти так, щоб будь-які двоє студентів могли безкоштовно спілкуватися, дорівнює \(n = 5\).

Для кожної пари різних студентів принаймні один із них вибрав іншого як безкоштовний контакт, тому будь-які двоє студентів можуть безкоштовно телефонувати один одному.