Lift

lift

Vellipo doreşte să viziteze întreg complexul Liftopolis, ce găzduieşte *Q* clădiri. Fiecare clădire are o singură uşă de intrare la nivelul 0 şi o singură uşă de ieşire, aflată la un nivel precizat. Orice clădire din complex are mai multe niveluri dispuse atât deasupra cât şi dedesubtul nivelului 0, niveluri la care se poate ajunge folosind un lift foarte interesant, care poate transporta o singură persoană la un moment dat. La intrarea în clădire, Vellipo va intra direct în lift, unde va da o succesiune cu număr minim de comenzi de urcare sau coborâre, pentru a ajunge la ieşire. Fiecare a *k*-a comandă va determina urcarea sau coborârea cu un număr de niveluri egal cu valoarea termenului de rang *k* din şirul lui Fibonacci. Vellipo trebuie să dea cel puţin o comandă când urcă în lift.

h2. Cerinţă

h2. Cerintă

Pentru fiecare dintre cele *Q* clădiri din Liftopolis, precizată prin nivelul la care se află uşa de ieşire din clădire, să se determine numărul minim de comenzi precum şi comenzile pe care Vellipo le va da pentru a ajunge la nivelul de ieşire.

* 1 ≤ *Q* ≤ 50.000
* pentru 20% dintre teste | *N* | ≤ 55 si | *Q* | ≤ 40
* pentru 40% dintre teste | *N* | ≤ 5000 si | *Q* |≤ 50000

* pentru 100% dintre teste | *N* | ≤ 10^15^ si | *Q* | ≤ 50000

* pentru 100% dintre teste | *N* | ≤ 10 15 si | *Q* | ≤ 50000

* Şirul lui Fibonacci: f ~1~ = 1, f ~2~ = 1, iar termenul de rang n este construit cu ajutorul relaţiei f ~n~ = f ~n-1~ + f ~n-2~ , n≥3
* Soluţia nu este unică. Orice soluţie corectă cu număr minim de comenzi este acceptată.