Sirtet

Υπάρχει ένα νέο φανταχτερό βιντεοπαιχνίδι μηδενικού προσώπου, το Sirtet. Το παιχνίδι είναι ένα ορθογώνιο πλέγμα με ~N~ σειρές και ~M~ στήλες. Πριν ξεκινήσει το παιχνίδι, ορισμένα κελιά του πλέγματος είναι κενά (σημειώνονται ως .) και άλλα γεμάτα (σημειώνονται ως #). Τα γεμάτα τετράγωνα αντιπροσωπεύουν ένα σύνολο αντικειμένων και τα γεμάτα τετράγωνα που είναι γειτονικά (οριζόντια ή κατακόρυφα) θα πρέπει να θεωρούνται μέρος του ίδιου άκαμπτου αντικειμένου. Για παράδειγμα, αυτό το αρχικό πλέγμα:

   ..#.
   ##.#
   .##.
   #...
   #...

έχει τέσσερα αντικείμενα, που φαίνονται παρακάτω:

   ##   #   #   #
    ##  #

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

Είσοδος

Η πρώτη γραμμή περιέχει δύο θετικούς ακέραιους, χωρισμένους με κενό, ~N~ και ~M~ (~N~ ~\cdot~ ~M~ ~\le~ ~10^6).

Οι επόμενες ~N~ γραμμές περιέχουν ~M~ χαρακτήρες η καθεμία, που περιγράφουν την αρχική κατάσταση του πλέγματος. Αν η ~j~-οστη στήλη της ~i~-οστης σειράς του πλέγματος περιέχει ένα αντικείμενο, ο αντίστοιχος χαρακτήρας στην είσοδο θα είναι #, αλλιώς θα είναι ..

Βαθμολογία

Για ~10~ από τους ~25~ διαθέσιμους βαθμούς, ~N~ ~\cdot~ ~M~ ~\le~ ~2\,000~.

Για επιπλέον ~6~ από τους ~25~ διαθέσιμους βαθμούς, ~M~ = ~2~.

Έξοδος

Εκτυπώστε ~N~ γραμμές που περιέχουν ~M~ χαρακτήρες η καθεμία που περιγράφουν την τελική κατάσταση του πλέγματος. Αν η ~j~-οστη στήλη της ~i~-οστης σειράς του πλέγματος περιέχει ένα αντικείμενο, ο αντίστοιχος χαρακτήρας θα είναι #, αλλιώς θα είναι ..

Παράδειγμα

input

5 4
..#.
##.#
.##.
#...
#...

output

...
...
###.
###.
#..#