Slikar

Ο Josip είναι ένας παράξενος ζωγράφος. Θέλει να ζωγραφίσει μια εικόνα που αποτελείται από ~N \times N~ εικονοστοιχεία (pixels), όπου το ~N~ είναι δύναμη του δύο (~1, 2, 4, 8, 16~ κ.λπ.). Κάθε εικονοστοιχείο θα είναι είτε μαύρο είτε λευκό. Ο Josip έχει ήδη μια ιδέα για το πώς το κάθε το εικονοστοιχείο θα χρωματιστεί.
Αυτό δεν θα ήταν πρόβλημα αν η διαδικασία ζωγραφικής του Josip δεν ήταν περίεργη. Χρησιμοποιεί την παρακάτω αναδρομική, διαδικασία:

  • Εάν η εικόνα είναι ένα μόνο εικονοστοιχείο, τη χρωματίζει όπως ήθελε.

  • Διαφορετικά, χωρίστε το τετράγωνο σε τέσσερα μικρότερα τετράγωνα και στη συνέχεια:

   1. Επιλέξτε ένα από τα τέσσερα τετράγωνα και χρωματίστε το λευκό.

   2. Επιλέξτε ένα από τα τρία τετράγωνα που απομένουν και χρωματίστε το μαύρο.

   3. Θεωρήστε τα δύο εναπομείναντα τετράγωνα ως νέους πίνακες και χρησιμοποιήστε την
    ίδια διαδικασία τριών βημάτων σε αυτους.

Σύντομα παρατήρησε ότι δεν ήταν δυνατό να μετατρέψει όλα τα οράματά του σε πίνακες με αυτή τη διαδικασία. Η δική σας δουλειά είναι να γράψετε ένα πρόγραμμα που θα ζωγραφίζει μια εικόνα που θα διαφέρει όσο το δυνατόν λιγότερο από την επιθυμητή εικόνα. Η διαφορά μεταξύ δύο εικόνων είναι ο αριθμός των ζευγών των εικονοστοιχείων στις αντίστοιχες θέσεις που διαφέρουν ως προς το χρώμα.

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό ~N (1 \le N \le 512)~, το μέγεθος της εικόνας που θα ήθελε να ζωγραφίσει ο Josip. Το ~N~ θα είναι δύναμη του ~2~.
Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει ~N~ ψηφία ~0~ ή ~1~, λευκά και μαύρα τετράγωνα στην εν λόγω εικόνα.

Έξοδος

Στην πρώτη γραμμή, τυπώστε τη μικρότερη δυνατή διαφορά που μπορεί να επιτευχθεί.
Στις επόμενες ~N~ γραμμές, τυπώστε μια εικόνα που μπορεί να ζωγραφιστεί με τη διαδικασία του Josip και επιτυγχάνει τη μικρότερη διαφορά. Η εικόνα πρέπει να έχει την ίδια μορφή όπως στην είσοδο.
Σημείωση: Το δεύτερο μέρος της εξόδου (η εικόνα) μπορεί να μην είναι μοναδικό. Οποιαδήποτε σωστή έξοδος θα γίνει αποδεκτή.

Βαθμολογία

Στα αρχεία ελέγχου αξίας ~50%~ πόντων, το ~N~ θα είναι το πολύ ~8~.

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

input

4
0001
0001
0011
1110

output

1
0001
0001
0011
1111

input

4
1111
1111
1111
1111

output

6
0011
0011
0111
1101

input

8
01010001
10100011
01010111
10101111
01010111
10100011
01010001
10100000

output

16
00000001
00000011
00000111
00001111
11110111
11110011
11110001
11110000