חברת טלפונים סלולריים מציעה את המבצע הבא: כל לקוח חדש רשאי לבחור בדיוק $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$. עבור כל זוג של סטודנטים שונים, לפחות אחד מהם בחר בשני, ולכן כל שניים יכולים לדבר בחינם.