Оператор мобильной связи предлагает следующую акцию: каждый новый клиент может выбрать ровно $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$. В каждой паре различных студентов хотя бы один выбрал другого, поэтому любые двое могут разговаривать бесплатно.