Ett mobiltelefonbolag erbjuder följande kampanj: varje ny kund får välja exakt $k$ andra telefonnummer och alla samtal mellan kunden och någon av de $k$ valda kontakterna är gratis (i båda riktningarna).
En grupp med $n$ studenter (numrerade från $1$ till $n$) vill utnyttja denna kampanj. Varje student $i$ måste välja exakt $k$ distinkta kontakter från mängden $\{1, 2, \dots, n\} \setminus \{i\}$.
Vi säger att två studenter $i$ och $j$ kan prata gratis om minst ett av följande gäller:
- $i$ har valt $j$ som en av sina gratiskontakter, eller
- $j$ har valt $i$ som en av sina gratiskontakter.
Studenterna vill välja sina gratiskontakter så att vilken student som helst kan prata med vilken annan student som helst gratis, dvs. för varje par $(i, j)$ med $1 \le i < j \le n$ kan studenterna $i$ och $j$ prata gratis.
För ett givet $k$ är din uppgift att:
- bestämma det maximalt möjliga antalet $n$ studenter för vilket en sådan konfiguration är möjlig,
- konstruera en giltig konfiguration av valda kontakter för detta maximala $n$.
Indata
Indatan består av ett enda heltal $k$.
Utdata
På den första raden, skriv ut ett enda heltal $n$ — det maximala antalet studenter för vilket det är möjligt att välja gratiskontakterna så att vilka två studenter som helst kan prata med varandra gratis.
På de följande $n$ raderna, skriv ut de $k$ gratiskontakter som valts av varje student: på rad $i+1$ (för $1 \le i \le n$), skriv ut $k$ distinkta heltal $a_{i,1}, a_{i,2}, \dots, a_{i,k}$. Varje $a_{i,j}$ måste uppfylla $1 \le a_{i,j} \le n$ och $a_{i,j} \neq i$. Dessa rader anger att student $i$ har valt studenterna $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ som sina gratiskontakter.
Om det finns flera giltiga svar, skriv ut vilket som helst av dem.
Begränsningar
- $1 \le k \le 1000$.
Exempel 1
2
5
2 5
3 4
1 5
1 3
2 4
Anmärkningar
I exemplet är $k = 2$ och det maximala antalet studenter för vilket det är möjligt att välja gratiskontakterna så att vilka två studenter som helst kan prata med varandra gratis är $n = 5$. För varje par av distinkta studenter har minst en av dem valt den andra, så vilka två som helst kan prata gratis.