Cerinţa

Dorel a fost răpit de extratereștri. Aceștia l-au dus pe nava lor intergalactică și pentru lunga călătorie spre planeta lor de baștină, au intrat în capsulele lor de hibernare. Dorel vrea să profite de această ocazie și să preia controlul navei. Ajuns în camera de comandă, descoperă n cercuri în care sunt scrise litere ca în imaginea de mai jos, obținută pentru n=5.

Pentru a prelua controlul navei și să se întoarcă acasă, Dorel trebuie să înlocuiască literele cu numere naturale distincte începând de la 1 până la numărul de litere astfel încât suma numerelor din oricare două cercuri să fie aceeași.

Neștiind ce este acesta, extratereștrii nu i-au luat lui Dorel telefonul. Dorel vă sună și vă roagă să il ajutați să găsească modalitatea de a inlocui literele cu cifre pentru a putea prelua controlul navei. Dorel vă trimite printr-un mesaj numărul de cercuri și vă roagă să îi trimiteți o modalitate prin care poate introduce numere în locul literelor, ca să preia controlul navei. Deoarece trebuie să se grăbească și numărul de cercuri se schimbă la fiecare două minute, Dorel are nevoie de prima soluție a problemei, în ordine lexicografică. Dacă îl ajutați, Dorel vă asigură recompensa va fi “galactică”.

Date de intrare

Fişierul de intrare cercuriabc1.in conţine pe prima linie numărul n, reprezentând numărul de cercuri.

Date de ieşire

Fişierul de ieşire cercuriabc1.out va conţine pe o linie, prima soluție în ordine lexicografică prin care Dorel poate prelua controlul navei. Numerele vor fi separate prin câte un spațiu.

Restricţii şi precizări

• 3 ≤ n ≤ 12
• Pentru orice număr n există soluție, deci Dorel poate prelua controlul navei cu ajutorul vostru.

Exemplu:

cercuriabc1.in

3

cercuriabc1.out

3 4 1 2 5  

Explicație

În cele 3 cercuri sunt 5 litere, de la A la E. Toate modalițățile de a pune numerele de la 1 la 5 în cele 3 cercuri sunt:

3 4 1 2 5 
4 2 3 1 5 
5 1 3 2 4 
5 2 1 4 3 

Soluția 3 4 1 2 5 este prima lexicografic și are următoarea distribuire a numerelor în cele 3 cercuri:
În primul cerc sunt numerele 3 și 4, în cel de-al doilea numerele 4, 1 și 2, iar în ultimul 2 și 5. Suma numerelor din fiecare cerc este egală cu 7, iar numerele sunt distincte.