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