33ος ΠΔΠ Καμπ (κοινά)
TWINGIFT2 (twingift2)

Έφτασαν πάλι τα γενέθλια του Ανδρέα και της Βάσως¹ και αυτή τη φορά είναι η σειρά του παππού να τους πάρει δώρα. Ο παππούς ξέρει ότι η Βάσω παίζει σκάκι και της αρέσει πολύ η σκακιέρα που έχει στο σαλόνι του, με τα μαρμάρινα πιόνια. Ξέρει ότι η Βάσω θα χαιρόταν πολύ αν της τη χάριζε και αυτό αποφασίζει να κάνει. Επίσης, και τα δύο παιδιά θαυμάζουν τη συλλογή νομισμάτων του παππού και αυτό του δίνει την ιδέα για το δώρο του Ανδρέα: θα του χαρίσει κάποια από τα νομίσματά του. Η μόνη δύσκολία που μένει στον παππού είναι πώς θα καταφέρει τα δώρα των δύο παιδιών να είναι ίσης αξίας…

Ο παππούς υπολογίζει ότι η σκακιέρα αξίζει \(B\) ευρώ. Η συλλογή νομισμάτων του περιέχει νομίσματα που οι αξίες τους είναι δυνάμεις του \(3\), έχει όμως ένα μόνο νόμισμα κάθε είδους — δηλαδή έχει ένα νόμισμα που αξίζει \(1\) ευρώ, ένα που αξίζει \(3\) ευρώ, ένα που αξίζει \(9\) ευρώ, ένα που αξίζει \(27\) ευρώ, κ.ο.κ. Ευτυχώς, η συλλογή του είναι πολύ μεγάλη (και ο παππούς πολύ πλούσιος) — μπορείτε να υποθέσετε ότι υπάρχουν άπειρα νομίσματα στη συλλογή του παππού, ένα για κάθε δύναμη του \(3\).

Προσπαθώντας να βρει ποια νομίσματα πρέπει να χαρίσει στον Ανδρέα έτσι ώστε οι αξίες τους να αθροίζουν σε \(B\) ευρώ, ο παππούς βλέπει ότι αυτό δε γίνεται πάντα (δηλαδή για όλες τις τιμές του \(B\)). Σκέφτεται ότι μπορεί να συμπληρώσει το δώρο της Βάσως με κάποια νομίσματα, έτσι ώστε η συνολική αξία των δώρων να είναι ίση και, καθώς είναι καλός στα μαθηματικά, αποδεικνύει ότι αυτό γίνεται πάντα.

Βοηθήστε τον παππού να βρει ποια νομίσματα πρέπει να δώσει στον Ανδρέα και ποια στη Βάσω (μαζί με τη σκακιέρα), έτσι ώστε η συνολική αξία των δώρων των δύο παιδιών να είναι ίση.

Αρχεία Εισόδου (twingift2.in):

Η πρώτη γραμμή της εισόδου θα περιέχει έναν θετικό ακέραιο αριθμό \(T\): το πλήθος των ερωτημάτων που το πρόγραμμά σας πρέπει να απαντήσει. Κάθε μία από τις επόμενες \(T\) γραμμές θα αντιστοιχεί σε ένα ερώτημα και θα περιέχει ένα θετικό ακέραιο αριθμό \(B\): την αξία της σκακιέρας.

Αρχεία Εξόδου (twingift2.out):

Η έξοδος πρέπει να περιέχει \(T\) γραμμές, κάθε μία από τις οποίες θα περιέχει την απάντηση στο αντίστοιχο ερώτημα της εισόδου. Η γραμμή πρέπει να περιέχει πρώτα τις αξίες των νομισμάτων που θα πάρει η Βάσω, σε αύξουσα σειρά, μετά το χαρακτήρα ‘#’ (δίεση) και μετά τις αξίες των νομισμάτων που θα πάρει ο Ανδρέας, σε αύξουσα σειρά. Όλα αυτά θα πρέπει να χωρίζονται ανά δύο με ένα κενό διάστημα. Αν για κάποιο ερώτημα υπάρχουν περισσότερες σωστές απαντήσεις, μπορείτε να τυπώσετε οποιαδήποτε από αυτές.

Παράδειγμα Αρχείου Εισόδου - Εξόδου:

twingift2.in	twingift2.out
3 42 30 17	3 9 27 # 81 # 3 27 1 9 # 27

Εξήγηση παραδείγματος: Στο πρώτο ερώτημα, η Βάσω θα πάρει τη σκακιέρα (\(42\)) και νομίσματα αξίας \(3\), \(9\) και \(27\), ενώ ο Ανδρέας ένα νόμισμα των \(81\) — ισχύει \(42 + 3 + 9 + 27 = 81\). Στο δεύτερο ερώτημα, η Βάσω θα πάρει μόνο τη σκακιέρα — ισχύει \(30 = 3 + 27\). Στο τρίτο ερώτημα ισχύει \(17 + 1 + 9 = 27\).

Περιορισμοί:

\(1 \leq T \leq 10\).
\(1 \leq B \leq 10^{18}\).
Όριο χρόνου εκτέλεσης: \(1\) sec.
Όριο μνήμης: \(64\) MB.

Subtasks

Για περιπτώσεις ελέγχου συνολικής αξίας 40%, θα είναι \(1 \leq B \leq 10^6\).