บริษัทโทรศัพท์มือถือแห่งหนึ่งจัดโปรโมชันดังนี้: ลูกค้าใหม่แต่ละคนสามารถเลือกหมายเลขโทรศัพท์อื่นได้พอดี $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$ สำหรับแต่ละคู่ของนักเรียนที่ต่างกัน อย่างน้อยหนึ่งคนในคู่ได้เลือกอีกคนหนึ่งไว้ ดังนั้นสองคนใดๆ จึงสามารถคุยกันได้ฟรี