Sim-4-2 | Florinel

Foarte lung, Florinel Coman... Hai, Florineeeeeel!

Cerință

Paul este un băiat aparte, care tot ce face este să se uite la anime și fotbal. Recent, a observat că a ajuns să cunoască tainele desenelor animate japoneze atât de bine încât în sfârșit acestea pot fi utilizate într-un mod productiv; anume, vrea să își regizeze propriul său anime.

Anime-ul lui Paul vizează calificarea României la Campionatul European de Fotbal din 2024. Ca atare, personajele principale sunt $2n + 1$ echipe de fotbal numerotate de la $1$ la $2n + 1$. Întrucât este la începutul conceperii scenariului și încă nu știe cum se va clasa România la Europene, Paul începe prin a scrie despre etapa grupelor. Toate aceste $2n + 1$ echipe de fotbal aparțin aceleiași grupe --- cea din care face parte România, desigur.

Paul a uitat faptul că orice meci de fotbal din fazele de calificare are și un meci de retur aferent; astfel, el va scrie câte un singur episod pentru fiecare pereche de două echipe. Deoarece Paul a uitat că pot să existe remize, fiecare meci din anime se va încheia prin victoria uneia dintre echipe, neexistând opțiunea unei remize. În total, Paul va scrie $N \cdot (2 \cdot N + 1)$ episoade.

Un anime nu este complet fără un rating, iar Paul își dorește ca anime-ul său să aibă un rating cât mai slab și o poveste cât mai inconsistentă, deoarece, cunoaștem cu toții că cele mai bune anime-uri se află mereu la coada clasamentului. Astfel, inconsistența scenariului este definită ca numărul de triplete de echipe distincte $(i, j, k)$ pentru care, în scenariul lui Paul, echipa $i$ va câștiga împotriva echipei $j$, echipa $j$ va câștiga împotriva echipei $k$, și echipa $k$ va câștiga împotriva echipei $i$.

Ajutați-l pe Paul să scrie cel mai slab anime posibil, spunându-i cum ar trebui să se termine fiecare episod!

Formal, fie $n$ un număr natural. Afișați o matrice binară (o matrice ce conține valori de $0$ sau $1$) cu $2n + 1$ rânduri și $2n + 1$ coloane, care respectă următoarele proprietăți:

• $A[i][j] \neq A[j][i]$ pentru oricare $i \neq j$;
• numărul de triplete $(i, j, k)$ cu $i \neq j \neq k$, pentru care $A[i][j] = A[j][k] = A[k][i] = 1$, este maxim.

Date de intrare

Pe prima linie se află un singur numâr întreg $n$.

Date de ieșire

Se vor afișa $2n + 1$ rânduri. Pe al $i$-lea rând se va găsi un șir de caractere de lungime $2n + 1$, reprezentând concatenarea valorilor de pe al $i$-lea rând din matricea $A$.

Restricții și precizări

Pentru toate testele, $1 \leq n \leq 1\ 000$. Mai apoi, pentru $42$ de puncte, se garanteaza ca $n \leq 100$.

Pentru fiecare test, soluția voastră va fi punctată în funcție de soluția optimă. Fie $S_{o}$ numărul maxim de triplete și $S_{c}$ numărul de triplete din soluția dată pe un anumit test. Notăm cu $x = S_{c}/S_{o}$. Punctajul obținut pe acel test este:

$\displaystyle punctaj_{test} \cdot min\left(\frac{2e^{2x}}{e^2 + e^{x + 1}} \times ( 0.8 x^{400} + 0.2 x), 1\right)$

Exemplu

stdin

1

stdout

001
100
010