한 이동통신사에서 다음과 같은 프로모션을 제공합니다. 각 신규 고객은 정확히 $k$개의 다른 전화번호를 선택할 수 있으며, 고객과 선택한 $k$명의 연락처 중 누구와도 모든 통화가 (양방향 모두) 무료입니다.
$n$명의 학생들로 이루어진 그룹($1$번부터 $n$번까지 번호가 매겨짐)이 이 프로모션을 이용하려고 합니다. 각 학생 $i$는 집합 $\{1, 2, \dots, n\} \setminus \{i\}$에서 서로 다른 연락처를 정확히 $k$명 선택해야 합니다.
다음 중 적어도 하나가 성립하면 두 학생 $i$와 $j$가 무료로 통화할 수 있다고 말합니다.
- $i$가 무료 연락처 중 하나로 $j$를 선택했거나,
- $j$가 무료 연락처 중 하나로 $i$를 선택했습니다.
학생들은 어떤 학생이든 다른 모든 학생과 무료로 통화할 수 있도록, 즉 $1 \le i < j \le n$인 모든 쌍 $(i, j)$에 대해 학생 $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$입니다. 서로 다른 두 학생의 모든 쌍에 대해 적어도 한 명이 다른 한 명을 선택했으므로, 어떤 두 학생이든 무료로 통화할 수 있습니다.