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