Una compañía de telefonía móvil ofrece la siguiente promoción: cada nuevo cliente puede elegir exactamente $k$ otros números de teléfono y todas las llamadas entre el cliente y cualquiera de los $k$ contactos elegidos son gratuitas (en ambas direcciones).
Un grupo de $n$ estudiantes (numerados del $1$ al $n$) quiere aprovechar esta promoción. Cada estudiante $i$ debe elegir exactamente $k$ contactos distintos del conjunto $\{1, 2, \dots, n\} \setminus \{i\}$.
Decimos que dos estudiantes $i$ y $j$ pueden hablar gratis si se cumple al menos una de las siguientes condiciones:
- $i$ ha elegido a $j$ como uno de sus contactos gratuitos, o
- $j$ ha elegido a $i$ como uno de sus contactos gratuitos.
Los estudiantes quieren elegir sus contactos gratuitos de modo que cualquier estudiante pueda hablar con cualquier otro estudiante gratis, es decir, para cada par $(i, j)$ con $1 \le i < j \le n$, los estudiantes $i$ y $j$ puedan hablar gratis.
Para un $k$ dado, tu tarea es:
- determinar el número máximo posible $n$ de estudiantes para el cual dicha configuración es posible,
- construir una configuración válida de contactos elegidos para este $n$ máximo.
Entrada
La entrada consta de un único entero $k$.
Salida
En la primera línea, imprime un solo entero $n$ — el número máximo de estudiantes para el cual es posible elegir los contactos gratuitos de manera que cualesquiera dos estudiantes puedan hablar entre sí gratis.
En las siguientes $n$ líneas, imprime los $k$ contactos gratuitos elegidos por cada estudiante: en la línea $i+1$ (para $1 \le i \le n$), imprime $k$ enteros distintos $a_{i,1}, a_{i,2}, \dots, a_{i,k}$. Cada $a_{i,j}$ debe satisfacer $1 \le a_{i,j} \le n$ y $a_{i,j} \neq i$. Estas líneas indican que el estudiante $i$ ha elegido a los estudiantes $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ como sus contactos gratuitos.
Si hay varias respuestas válidas, imprime cualquiera de ellas.
Restricciones
- $1 \le k \le 1000$.
Ejemplo 1
2
5
2 5
3 4
1 5
1 3
2 4
Notas
En el ejemplo, $k = 2$ y el número máximo de estudiantes para el cual es posible elegir los contactos gratuitos de forma que cualesquiera dos estudiantes puedan hablar entre sí gratis es $n = 5$. Para cada par de estudiantes distintos, al menos uno de ellos ha elegido al otro, por lo que cualesquiera dos pueden hablar gratis.