Sateliti

Για τους σκοπούς της εξερεύνησης ενός κρατήρα, το τηλεσκόπιο Arecibo καταγράφει εικόνες των δορυφόρων του Κρόνου. Η επιστημονική ομάδα πρέπει να διαχωρίσει τις δορυφορικές εικόνες και να τις ομαδοποιήσει ανά δορυφόρο, αλλά δεν είναι τόσο απλό γιατί οι δορυφόροι θα μπορούσαν να ληφθούν από διαφορετικές γωνίες.

Οι ληφθείσες εικόνες μπορούν να εμφανιστούν ως πίνακες ~n \times m~, γεμάτες με '*' (κρατήρας) και '.' (απλή επιφάνεια). Λέμε ότι δύο εικόνες αντιστοιχούν στον ίδιο δορυφόρο εάν από τη μία μπορούμε να πάρουμε την άλλη με κυκλικές μετατοπίσεις σειρών και στηλών.

Για να διευκολύνουν τη διαδικασία επαλήθευσης, οι επιστήμονες θέλουν να βρουν τη λεξικογραφικά μικρότερη εικόνα που αντιστοιχεί στον δορυφόρο από τη δεδομένη εικόνα. Όταν συγκρίνουμε εικόνες, συγκρίνουμε συμβολοσειρές που λαμβάνονται με τη σύνδεση όλων των σειρών της εικόνας, όπου οι χαρακτήρες συγκρίνονται με βάση την τιμή τους στον πίνακα ASCII.

Είσοδος

Η πρώτη γραμμή περιέχει ακέραιους αριθμούς ~n~ και ~m\;(1 \le n, m \le 1\,000)~, τις διαστάσεις της εικόνας.

Κάθε μία από τις ακόλουθες ~n~ γραμμές περιέχει ~m~ χαρακτήρες '*' και '.'. Αυτό αντιπροσωπεύει την εικόνα που τραβήχτηκε.

Έξοδος

Περιλαμβάνει ~n~ γραμμές με ~m~ χαρακτήρες η καθεμία, δηλαδή την επιθυμητή, λεξικογραφικά μικρότερη, εικόνα.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	~1 \le n, m \le 50~
2	40	~1 \le n, m \le 300~
3	60	Κανένας επιπλέον περιορισμός.

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

input

3 3
.**
*..
.*.

output

**.
..*
*..

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

Όλες οι εικόνες που μπορούν να ληφθούν με κυκλικές εναλλαγές είναι:

.**    .*.    *..    **.    *..    ..*    *.*    ..*    .*.
*..    .**    .*.    ..*    **.    *..    .*.    *.*    ..*
.*.    *..    .**    *..    ..*    **.    ..*    .*.    *.*

input

3 4
....
..*.
....

output

*...
....
....

input

3 5
.**..
.***.
..**.

output

***..
.**..
**...