Carnial General

Κάθε τέσσερα χρόνια, οι φοιτητές του Lund συγκεντρώνονται για να οργανώσουν το καρναβάλι του Lund. Για λίγες ημέρες, ένα πάρκο γεμίζει με σκηνές όπου λαμβάνουν χώρα κάθε είδους εορταστικές δραστηριότητες. Το άτομο που είναι υπεύθυνο για την πραγματοποίηση αυτού του γεγονότος είναι ο πρωτομάστορας του καρναβαλιού.

Συνολικά, έχουν γίνει ~N~ καρναβάλια, το καθένα με διαφορετικό πρωτομάστορα. Οι πρωτομάστορες είναι αριθμημένοι από ~0~ έως ~N - 1~ με χρονολογική σειρά. Κάθε πρωτομάστορας ~i~ έχει δώσει τη γνώμη του για το πόσο καλοί ήταν οι προκάτοχοί του, δημοσιεύοντας μια κατάταξη των πρωτομαστόρων ~0, 1, \cdots, i - 1~ με σειρά από τον καλύτερο προς τον χειρότερο.

Το επόμενο καρναβάλι του Lund θα γίνει το ~2026~. Εν τω μεταξύ, όλοι οι προηγούμενοι πρωτομάστορες του καρναβαλιού έχουν συγκεντρώθει για να βγάλουν μια ομαδική φωτογραφία. Ωστόσο, θα ήταν άβολο αν οι πρωτομάστορες ~i~ και ~j~ (όπου ~i < j~) καταλήγουν να στέκονται ο ένας δίπλα στον άλλον, αν ο ~i~ βρίσκεται αυστηρά στο δεύτερο μισό της κατάταξης του ~j~.

Για παράδειγμα:

• Εάν ο πρωτομάστορας ~4~ έχει δημοσιεύσει την κατάταξη ~3\,2/,1/,0~, τότε ο ~4~ μπορεί να σταθεί δίπλα στον ~3~, ή στον ~2~, αλλά όχι στον ~1~ ή στον ~0~.
• Εάν ο πρωτομάστορας ~5~ έχει δημοσιεύσει την κατάταξη ~4/,3/,2/,1/,0~, τότε ο ~5~ μπορεί να σταθεί δίπλα στον ~4~, στον ~3~ ή στον ~2~, αλλά όχι στον ~1~ ή στον ~0~. Σημειώστε ότι δεν πειράζει αν ένας πρωτομάστορας βρίσκεται ακριβώς στη μέση της κατάταξης ενός άλλου.

Το ακόλουθο σχήμα απεικονίζει το παράδειγμα ~1~. Εδώ, ο πρωτομάστορας ~5~ στέκεται δίπλα στους πρωτομάστορες ~2~ και ~3~ και ο πρωτομάστορας ~4~ στέκεται μόνο δίπλα στον πρωτομάστορα ~2~.

Σας δίνονται οι κατατάξεις που δημοσίευσαν οι πρωτομάστορες. Στόχος σας είναι να τοποθετήσετε τους πρωτομάστορες ~0, 1, \cdots, N - 1~ σε μια σειρά, έτσι ώστε αν ~i~ και ~j~ είναι γειτονικοί (όπου ~i < j~), τότε ο ~i~ δεν είναι αυστηρά στο δεύτερο μισό της κατάταξης του ~j~.

Είσοδος

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

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

Πιο συγκεκριμένα, η κατάταξη του πρωτομάστορα ~i~ είναι μια λίστα με ~i~ ακέραιους ~p_{i, 0}, p_{i, 1}, \cdots, p_{i, i-1}~ στην οποία κάθε ακέραιος από ~0~ έως ~i - 1~ εμφανίζεται ακριβώς μία φορά. Ο ~p_{i, 0}~ είναι ο καλύτερος και ο ~p_{i, i-1}~ ο χειρότερος πρωτομάστορας σύμφωνα με τον πρωτομάστορα ~i~.

Έξοδος

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

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

Περιορισμοί και βαθμολογία

• ~2 \le N \le 1\,000~
• ~0 \le p_{i, 0}, p_{i, 1}, \cdots, p_{i, i-1} \le i - 1~ για ~i = 0, 1, \cdots, N - 1~.

Η λύση σας θα δοκιμαστεί σε ένα σύνολο ομάδων δοκιμών (test groups), καθεμία από τις οποίες αξίζει έναν αριθμό βαθμών. Κάθε test group περιέχει ένα σύνολο δοκιμαστικών περιπτώσεων (test cases). Για να λάβετε τους πόντους για ένα test group, πρέπει να επιλύσετε όλα τα test cases στο test group.

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~11~	Η κατάταξη του πρωτομάστορα ~i~ θα είναι ~i - 1, i - 2, \cdots, 0~ για όλα τα ~i~, έτσι ώστε ~1 \le i \le N - 1~.
~2~	~23~	Η κατάταξη του πρωτομάστορα ~i~ θα είναι ~0, 1, \cdots,i - 1~ για όλα τα ~i~ έτσι ώστε ~1 \le i \le N - 1~.
~3~	~29~	~N \le 8~
~4~	~37~	Κανένας επιπλέον περιορισμός.

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

input

6
0
1 0
2 1 0
3 2 1 0
4 3 2 1 0

output

4 2 5 3 1 0

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

Το παράδειγμα ικανοποιεί τους περιορισμούς του test group ~1~. Σε αυτό το παράδειγμα, ούτε ο πρωτομάστορας ~2~, ούτε ο πρωτομάστορας ~3~ μπορούν να σταθούν δίπλα στον πρωτομάστορα ~0~ και ούτε ο πρωτομάστορας ~4~, ούτε ο πρωτομάστορας ~5~ μπορούν να σταθούν δίπλα στους πρωτομάστορες ~0~ και ~1~. Η έξοδος του παραδείγματος απεικονίζεται στην παραπάνω εικόνα.

input

5
0
0 1
0 1 2
0 1 2 3

output

2 0 4 1 3

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

Το παράδειγμα ικανοποιεί τους περιορισμούς του test group ~2~. Σε αυτό το παράδειγμα, ο πρωτομάστορας ~2~ δεν μπορεί να σταθεί δίπλα στον πρωτομάστορα ~1~, ο πρωτομάστορας ~3~ δεν μπορεί να σταθεί δίπλα στον πρωτομάστορα ~2~ και ο πρωτομάστορας ~4~ δεν μπορεί να σταθεί δίπλα στους πρωτομάστορες ~3~ και ~2~.

input

4
0
1 0
0 2 1

output

3 0 1 2

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

Το παράδειγμα ικανοποιεί τους περιορισμούς του test group ~3~. Σε αυτό το παράδειγμα, τα μόνα ζεύγη πρωτομαστόρων που δεν μπορούν να σταθούν δίπλα δίπλα είναι τα ~(1, 3)~ και ~(0, 2)~. Επομένως, δεν υπάρχουν συγκρούσεις αν είναι τοποθετημένοι με τον τρόπο ~3\,0\,1\,2~. Μια άλλη πιθανή απάντηση είναι η ~0\,1\,2\,3~.