Jogurt

Ένα πλήρες δυαδικό δέντρο αποτελείται από κόμβους διατεταγμένους σε μια ιεραρχική δομή. Ένας από τους κόμβους είναι η ρίζα, που θεωρείται ότι βρίσκεται στο επίπεδο ~0~. Ο ριζικός κόμβος έχει δύο θυγατρικούς κόμβους, οι οποίοι βρίσκονται στο επίπεδο ~1~. Καθένας από αυτούς έχει δύο παιδιά στο επίπεδο ~2~ κ.λπ.
Γενικά, ένα πλήρες δυαδικό δέντρο με ~N~ επίπεδα έχει ~2^N-1~ κόμβους, καθένας από τους οποίους έχει δύο θυγατρικούς κόμβους, εκτός από αυτούς στο επίπεδο ~L-1~.
Ένας αριθμός μπορεί να γραφτεί σε κάθε κόμβο. Γράψτε τους αριθμούς ~1~ έως ~2^N-1~ σε ένα πλήρες δυαδικό δέντρο με ~N~ επίπεδα έτσι ώστε, για κάθε κόμβο στο επίπεδο ~D~, η απόλυτη τιμή της διαφοράς του αθροίσματος όλων των αριθμών στο αριστερό υποδέντρο και του αθροίσματος όλων των αριθμών στο δεξί υποδέντρο να είναι ~2^D~.
Για παράδειγμα, το άθροισμα των αριθμών του αριστερού υποδέντρου του ριζικού κόμβου πρέπει να διαφέρει από το άθροισμα των αριθμών του δεξιού υποδέντρου κατά ~1~. Τα αθροίσματα των αριθμών του αριστερού και των αριθμών του δεξιού υποδέντρου ενός κόμβου στο επίπεδο ~1~ πρέπει να διαφέρουν κατά ~2~.

Κάθε αριθμός πρέπει να χρησιμοποιειθεί ακριβώς μία φορά. Η λύση δεν χρειάζεται να είναι μοναδική.

Είσοδος

Η πρώτη και μοναδική γραμμή εισαγωγής περιέχει τον ακέραιο αριθμό ~N (1 \le N \le 15)~, τον αριθμό των επιπέδων στο δέντρο.

Έξοδος

Εκτυπώστε τούς ~2^N-1~ διαχωρισμένους με κενά αριθμούς σε μία γραμμή, το δυαδικό δέντρο στην προδιατεταγμένη διέλευση.Η προδιατεταγμένη διέλευση εκτυπώνει πρώτα τον αριθμό στον ριζικό κόμβο και μετά εκτυπώνει το αριστερό υποδέντρο (και πάλι στη προδιατεταγμένη διέλευση), μετά το δεξί υποδέντρο.

Παραδείγματα

input

2

output

3 1 2

input

3

output

3 1 7 5 6 2 4