puteri35

După ce au învăţat la şcoală numerele, Maria si Mihai au început sa se joace cu ele. Maria şi-a ales numărul $3$ şi a spus că îi plac toate numerele ce se pot scrie ca sumă de una sau mai multe puteri distincte ale lui $3$. De exemplu: $1 = 3 ^ 0, 91 = 3 ^ 4 + 3 ^ 2 + 3 ^ 0, 27 = 3 ^ 3$, sunt numere care îi plac Mariei. Numărul $6 = 3 ^ 2 + 3 ^ 2$ nu îi place Mariei ($3 ^ 2$ apare de $2$ ori). Mihai, căruia îi place mereu să intre în competiţie cu Maria, a ales numărul $5$ şi a zis că îi plac numerele ce se pot scrie ca sumă de una sau mai multe puteri distincte ale lui $5$ (aceeaşi regulă ca la numerele care îi plac Mariei, dar folosind numărul $5$). Jucându-se pe calculator, au găsit un fişier puteri35.in în care era scris un număr natural nenul $n$. Imediat, copii s-au gândit să scrie fiecare într-un fişier (pe care de comun acord l-au numit puteri35.out), fiecare, primele $n$ numere care îi plac. Aici a apărut din nou discuţia: în ce ordine le vor scrie. În sfârşit, au căzut de acord să scrie toate cele $2 \cdot n$ numere în ordine crescătoare.

Cerinţă

Dându-se un număr natural nenul $n$, obţineţi în ordine crescătoare toate cele $2 \cdot n$ numere, primele $n$ numere care îi plac Mariei şi primele $n$ care îi plac lui Mihai.

Date de intrare

Fişierul de intrare puteri35.in conţine pe prima linie un număr natural $n$.

Date de ieşire

Fişierul de ieşire puteri35.out conţine $2 \cdot n$ numere, fiecare pe câte o linie, în ordine crescătoare, primele $n$ numere care îi plac Mariei si primele $n$ numere care îi plac lui Mihai.

Restricţii şi precizări

• $1 \leq n \leq 1 \ 000 \ 000$

Exemplu

puteri35.in

3

puteri35.out

1
1
3
4
5
6

Explicaţie

Soluţia $1 \ 3 \ 4 \ 1 \ 5 \ 6$ nu este corectă pentru că numerele nu sunt în ordine crescătoare