The Filter

Η Αλίκη, η μαθηματικός, θέλει να μελετά πραγματικούς αριθμούς που βρίσκονται μεταξύ του ~0~ και του ~1~. Το αγαπημένο της εργαλείο είναι το φίλτρο.

Ένα φίλτρο καλύπτει ένα μέρος της αριθμητικής γραμμής. Όταν ένας αριθμός φτάσει στο φίλτρο, δύο πράγματα μπορούν να συμβούν. Αν ένας αριθμός δεν καλύπτεται από το φίλτρο, ο αριθμός θα περάσει. Εάν ένας αριθμός καλύπτεται, ο αριθμός θα αφαιρεθεί.

Η Αλίκη έχει άπειρα πολλά φίλτρα. Τα 3 πρώτα της φίλτρα μοιάζουν ως εξής:

Γενικά, το ~k~-οστό φίλτρο μπορεί να οριστεί ως εξής:

• Θεωρήστε την αριθμητική γραμμή από το ~0~ έως το ~1~.
• Χωρίστε αυτή την αριθμητική γραμμή σε ~3^{k}~ κομμάτια ίσου μεγέθους. Υπάρχουν ~3^{k}+1~ σημεία και 3k διαστήματα.
• Το ~k~-οστό φίλτρο αποτελείται από το 2ο διάστημα, το 5ο διάστημα, το 8ο διάστημα και γενικά το ~(3i - 1)~-οστό διάστημα. Τα σημεία δεν αποτελούν μέρος του ~k~-οστού φίλτρου.

Η Αλίκη έχει οδηγίες για την κατασκευή του συνόλου Cantor. Ξεκινήστε με την αριθμητική γραμμή από το ~0~ έως το ~1~. Εφαρμόστε όλα τα φίλτρα στην αριθμητική γραμμή και αφαιρέστε τους αριθμούς που καλύπτονται. Οι εναπομείναντες αριθμοί σχηματίζουν το σύνολο Cantor.

Η Alice θέλει να ερευνήσει το σύνολο Cantor και ήρθε σε εσάς για βοήθεια. Δεδομένου ενός ακέραιου αριθμού ~N~, η Αλίκη θα ήθελε να μάθει ποια κλάσματα ~\frac{x}{N}~ ανήκουν στο σύνολο Cantor.

Είσοδος

Η πρώτη γραμμή θα περιέχει τον ακέραιο αριθμό ~N~.

Για ~3~ από τους ~15~ διαθέσιμους βαθμούς, ~3 \le N \le 3^{18}~ και το ~N~ είναι μια δύναμη του ~3~.

Για επιπλέον ~4~ από τους ~15~ διαθέσιμους βαθμούς, ~2 \le N \le 10^{5}~.

Για επιπλέον ~8~ από τους ~15~ διαθέσιμους βαθμούς, ~2 \le N \le 10^{9}~.

Έξοδος

Εξάγετε όλους τους ακέραιους αριθμούς ~x~ όπου ~0 \le x \le N~ και ~\frac{x}{N}~ ανήκουν στο σύνολο Cantor.

Εξάγετε τις απαντήσεις σε αύξουσα σειρά. Ο αριθμός των απαντήσεων δεν θα υπερβαίνει τις ~10^{6}~.

Παράδειγμα

input

12

output

0
1
3
4
8
9
11
12

Επεξήγηση του παραδείγματος:

Ακολουθεί ένα διάγραμμα των κλασμάτων και των πρώτων ~4~ φίλτρων. Στην πραγματικότητα, υπάρχουν άπειρα φίλτρα.

~\frac{5}{12}~, ~\frac{6}{12}~ και ~\frac{7}{12}~ δεν περιλαμβάνονται στο σύνολο Cantor, επειδή καλύφθηκαν από το ~1~ο φίλτρο.

Επιπλέον, τα ~\frac{2}{12}~ και ~\frac{10}{12}~ δεν ανήκουν στο σύνολο Cantor επειδή καλύφθηκαν από το ~2~ο φίλτρο.

Μπορεί να αποδειχθεί ότι τα υπόλοιπα κλάσματα θα περάσουν από όλα τα φίλτρα.