plimbare

Zaharel a iesit la o plimbare. El va merge de la punctul de coordonate (0, 0, 0) la punctul de coordonate (X, Y, Z). Se stie ca Zaharel merge mai ciudat: dintr-o pozitie (x1, y1, z1) el va merge doar intr-o pozitie de forma (x1±2n, y1±2n, z1±2n) unde n este un numar natural. In plus, plimbarea de astazi este mai speciala, in sensul ca Zaharel nu va folosi decat valori distincte pentru n.

Cerinta

Dandu-se numerele X Y Z sa se determine un traseu cu numar minim de pozitii pentru ca Zaharel sa ajunga de la (0, 0, 0) la (X, Y, Z).

Date de intrare

Pe prima linie a fisierului de intrare plimbare.in sunt se vor gasi numerele naturale X Y Z, separate prin spatii.

Date de iesire

Prima linie a fisierului plimbare.out va contine un singur numar natural Pmin reprezentand numarul minim de pozitii. Urmatoarele Pmin linii vor contine cate trei numere intregi pe o linie, reprezentand pozitiile (X, Y, Z) prin care trece Zaharel.

Restrictii

0 <= X,Y,Z <= 1018
Se garanteaza ca pentru datele de test exista solutie.
Daca exista mai multe trasee cu numar minim de pasi se va afisa acela care este minim lexicografic.  Spunem ca un traseu A=(A1, A2..., An) (Ai=(AiX,AiY,AiZ)) este mai mic din punct de vedere lexicografic decat un alt traseu B=(B1, B2, ..., Bn) (Bi=(BiX, BiY, BiZ)) daca exista o pozitie 1<=i<=N astfel incat A1=B1, A2=B2, ..., Ai-1=Bi-1 si Ai<Bi.
O pozitie A=(AX, AY, AZ) este mai mica din punct de vedere lexicografic decat o alta pozitie B=(BX, BY, BZ)  daca: (a) AX<BX sau (b) AX=BX si AY<BY sau (c) AX=BX si AY=BY si AZ<BZ

Exemple

plimbare.in

plimbare.out plimbare.in

plimbare.out

16 16 16

2
0 0 0
16 16 16

 123 213 321

10
0 0 0
-128 -128 128
-192 -64 64
-194 -62 62
-193 -63 61
-189 -67 57
-181 -59 49
-165 -75 33
-133 -43 65
123 213 321

Timp maxim de executie/test: 0.2 secunde

Mircea Paşoi
Universitatea Bucuresti,Facultatea de Matematica si Informatica
mircea@infoarena.ro