Trapezi

Μπορούμε να δημιουργήσουμε ένα εξαγωνικό παζλ μεγέθους ~n~ διαιρώντας ένα κανονικό εξάγωνο σε ισόπλευρα τρίγωνα σχεδιάζοντας ~2n - 1~ ισαπέχουσες παράλληλες γραμμές μεταξύ κάθε τριών ζευγών απέναντι πλευρών του εξαγώνου. Κάποια από τα τρίγωνα στο παζλ είναι σκιασμένα και πρέπει να καλυφθούν με κομμάτια παζλ. Κάθε κομμάτι είναι ένα τραπέζιο που αποτελείται από τρία ισόπλευρα τρίγωνα τοποθετημένα το ένα δίπλα στο άλλο. Τα κομμάτια έρχονται σε ~6~ διαφορετικά χρώματα που σθμβολίζονται με αριθμούς από το ~1~ έως το ~6~, και έχουμε στη διάθεσή μας απεριόριστο αριθμό τεμαχίων από κάθε χρώμα.

Παζλ μεγέθους 3 από το πρώτο παράδειγμα και μία λύση

Ο στόχος του παζλ είναι να βάλεις τα κομμάτια στο εξάγωνο έτσι ώστε να ισχύει το εξής:

1. Κάθε κομμάτι τοποθετείται έτσι ώστε να καλύπτει πλήρως τρία σκιασμένα τρίγωνα.
   
2. Κάθε σκιασμένο τρίγωνο καλύπτεται από ένα ακριβώς κομμάτι.
   
3. Δύο κομμάτια του ίδιου χρώματος δεν ακουμπούν κατά μήκος της πλευράς ενός τριγώνου (μπορούν να ακουμπήσουν σε μια γωνία).
   

Προσδιορίστε εάν είναι δυνατό να λύσετε το δεδομένο παζλ και, αν είναι, βρείτε μία λύση.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο ~n~ - το μέγεθος του παζλ. Οι ακόλουθες ~2n~ γραμμές περιγράφουν τις σειρές του παζλ από πάνω προς τα κάτω. Κάθε μία από αυτές τις γραμμές περιέχει μια συμβολοσειρά που περιγράφει τα τρίγωνα σε μια σειρά του παζλ από αριστερά προς τα δεξιά. Το ψηφίο "~0~" υποδηλώνει ένα σκιασμένο τρίγωνο, ενώ "~.~" (τελεία) δηλώνει τρίγωνο που δεν είναι σκιασμένο. Μπορείτε να υποθέσετε ότι τουλάχιστον ένα τρίγωνο θα είναι σκιασμένο.

Έξοδος

Εάν το παζλ είναι αδύνατο να λυθεί, εκτυπώστε στην πρώτη γραμμή «nemoguce» (κροατική λέξη για αδύνατο). Σε διαφορετική περίπτωση, εκτυπώστε στην έξοδο ~2n~ γραμμές που περιγράφουν τη λύση στην ίδια μορφή με το παζλ που δίνεται στην είσοδο. Σκιασμένα τρίγωνα πρέπει να συμβολίζονται με ένα από τα ψηφία "~1~" έως το "~6~", αντί για το ψηφίο "~0~". Τα ψηφία αντιπροσωπεύουν το χρώμα των κομματιών με το οποίο καλύπτεται το τρίγωνο.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	6	~n=1~
2	17	~n=2~
3	18	~n=3~
4	22	~n=4~
5	37	~n=5~

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

input

3
.000000
...000000
.....000000
.....0.....
...000...
.00000.

output

.111224
...332442
.....311122
.....1.....
...112...
.33322.

input

1
.0.
0.0

output

nemoguce

input

2
0000.
0000000
..00.0.
.0000

output

1222.
1133111
..31.2.
.1122