Consideram ca avem 3 stalpi (numerotati 1, 2, 3) si 2N discuri. N discuri sunt albe si au dimensiunile diametrelor distincte, cuprinse intre 1 si N. Celelalte N discuri sunt negre si au de asemenea dimensiunile diametrelor distincte, cuprinse intre 1 si N. Aceste discuri sunt asezate pe primii doi stalpi (N pe stalpul 1 si N pe stalpul 2), in ordine strict descrescatoare a dimensiunii diametrelor, in culori alternante.
De exemplu pentru N = 3 pe primul stalp vom avea (de jos in sus): discul de dimensiune 3 alb, discul de dimensiune 2 negru, discul de dimensiune 1 alb. Iar pe stalpul 2: discul de dimensiune 3 negru, discul de dimensiune 2 alb si discul de dimensiune 1 negru.
Mutarile permise sunt mutarea unui disc din varful unui stalp pe alt stalp (tot in varf), cu conditia ca discul peste care se muta sa aiba dimensiune cel putin egala cu a celui mutat. Intrucat exista cate doua discuri de aceeasi dimensiune, acestea pot fi puse oricum unul peste altul.

Cerinta

Scrieti un program care sa determine un sir de mutari dupa a caror executare pe un stalp sa se afle N discuri albe, pe unul N discuri negre, iar unul sa fie gol.

Date de intrare

Pe prima linie a fisierului de intrare hanoi.in este scris N.

Date de iesire

Fisierul hanoi.out va contine o succesiune de mutari, cate o mutare pe linie. O mutare este descrisa de o pereche de numere naturale separate printr-un spatiu; primul numar este stalpul de pe care se ia discul, iar al doilea numar este stalpul pe care se pune discul. Aceste doua numere pot fi numai 1, 2 sau 3.
Pe ultima linie a fisierului de iesire va fi trecut numarul 0, care semnifica terminarea mutarilor.

Restrictii

• 1 <=N <= 16
• Nu trebuie numar minim de mutari insa numarul de mutari trebuie sa fie de maxim 400 000

Exemplu

student Marius Andrei
Facultatea de Automatica si Calculatoare
Contact: marsamg@yahoo.com