Pornind de la numărul 1,orice număr natural se poate obţine aplicând repetat în mod convenabil operaţii din cele de mai jos:

• înmulţire cu 3
• adunare cu 1
• scădere cu 1

De exemplu numărul 24 se poate obţine astfel:

Adunăm 1: 1 + 1 = 2
Adunăm 1: 2 + 1 = 3
Înmultim cu 3: 3 * 3 = 9
Scădem 1: 9 - 1 = 8
Înmulțim cu 3: 8 * 3 = 24

Urmărind operaţiile de la stânga la dreapta pentru exemplul de mai sus, şirul de operaţii se codifică cu 1, 1, 3, -1, 3.

Cerinţă

Cunoscând numărul natural n,să se tipărească şirul de operaţii prin care se poate ajunge de la numărul iniţial 1 la numărul final n.

Date de intrare

Fişierul de intrare n311.in conţine pe prima linie valoarea numărului natural n.

Date de ieşire

Fişierul de ieşire n311.out va conţine pe prima linie şirul de operaţii format din numere întregi separate prin câte un spaţiu, cu semnificaţia de mai sus.

Restricţii şi precizări

• 1 < n <= 2 000 000000;
• Pot exista mai multe soluţii, se acceptă oricare, dacă se încadrează în timpul de execuţie;
• Nu este obligatorie folosirea tuturor tipurilor de operaţii.

Exemple

Exemplul 1

n311.in

24

n311.out

1 1 3 -1 3

Exemplul 2

n311.in

4

n311.out

1 1 1