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 = 30, 91=34+32+30, 27 = 33, sunt numere care îi plac Mariei. Numărul 6 = 31 + 31 nu îi place Mariei (31 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, copiii 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•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•n numere, primele n numere care îi plac Mariei şi primele n care îi plac lui Mihai.
Date de intrare
Fişierul puteri35.in conţine pe prima linie un număr natural n.
Date de ieşire
Fişierul puteri35.out conţine 2•n numere, fiecare pe câte o linie, în ordine crescătoare, primele n numere care îi plac Mariei şi primele n numere care îi plac lui Mihai.
Restricţii
n<=1000 000
Exemple
puteri35.in
puteri35.out
Explicaţii
3
1
1
3
4
5
6
Soluţia 1 3 4 1 5 6 nu este corectă pentru că numerele nu sunt în ordine crescătoare.