Reljef

Δύο ομάδες ανθρώπων των σπηλαίων μπήκαν σε μια διαμάχη για τη γη και αποφάσισαν να τη διευθετήσουν με τον παλιό 'καλό' τρόπο, πετώντας ρόπαλα ο ένας στον άλλο. Ο αγώνας οργανώθηκε σε μια σπηλιά, τόσο ψηλή ώστε το ταβάνι να μην προκαλεί ανησυχία, αλλά τα κοιτάσματα ορυκτών στο έδαφος εμποδίζουν τα ιπτάμενα ρόπαλα.

Το σπήλαιο μπορεί να χωριστεί σε ~R~ σειρές και ~C~ στήλες, έτσι ώστε ολόκληρο το σπήλαιο να αποτελείται από ~R \times C~ κελιά. Καθε κελί στη σπηλιά είναι είτε άδειο είτε περιέχει ένα κομμάτι ορυκτού. Δύο κομμάτια ορυκτών αποτελούν μέρος του ίδιου συμπλεγμάτος εάν είναι γειτονικά σε μία από τις τέσσερις κύριες κατευθύνσεις (πάνω, κάτω, αριστερά, δεξιά).

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

Εάν το ρόπαλο χτυπήσει ένα κομμάτι ορυκτού στο δρόμο, καταστρέφει το κομμάτι, το κελί αδειάζει και το το ρόπαλο σταματά το ταξίδι του.

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

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

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς ~R~ και ~C~ ~(1 \le R, C \le 100)~, τις διαστάσεις του σπηλαίου.

Κάθε μία από τις ακόλουθες γραμμές ~R~ θα περιέχει ~C~ χαρακτήρες. Ο χαρακτήρας '.' αντιπροσωπεύει ένα κενό κελί, ενώ ο χαρακτήρας '~x~' αντιπροσωπεύει ένα κομμάτι ορυκτού.

Η επόμενη γραμμή περιέχει έναν ακέραιο αριθμό ~N~ ~(1 \le N \le 100)~, τον αριθμό των ροπάλων που πετάχτηκαν.

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

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

Έξοδος

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

Πραδείγματα

input

5 6
......
..xx..
..x...
..xx..
.xxxx.
1
3

output

......
......
..xx..
..xx..
.xxxx.

input

8 8
........
........
...x.xx.
...xxx..
..xxx...
..x.xxx.
..x...x.
.xxx..x.
5
6 6 4 3 1

output

........
........
........
........
.....x..
..xxxx..
..xxx.x.
..xxxxx.

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

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

input

7 6
......
......
xx....
.xx...
..xx..
...xx.
....x.
2
6 4

output

......
......
......
......
..xx..
xx.xx.
.x..x.