Blindfold

Η Rose και ο Colin παίζουν ένα παιχνίδι στην αυλή τους. Δεδομένου ότι η πίσω αυλή είναι ορθογώνια, μπορούμε να τη σκεφτούμε ως ένα πλέγμα με ~r~ σειρές και ~c~ στήλες. Η Rose και ο Colin βάζουν εμπόδια σε μερικά από τα τετράγωνα.

Το παιχνίδι παίζεται ως εξής:
Ο Colin δένει τα μάτια του και η Rose τον μεταφέρει σε κάποιο τετράγωνο πλέγμα (grid square) στην πίσω αυλή. Τον βάζει κάτω έτσι ώστε να κοιτάζει βόρεια, νότια, ανατολικά ή δυτικά. Ο Colin δεν γνωρίζει αυτήν την αρχική θέση ή την κατεύθυνση.
Στη συνέχεια, η Rose δίνει εντολή στον Colin να κάνει μια σειρά από κινήσεις στην πίσω αυλή. Κάθε κίνηση είναι μία από τις ακόλουθες:

• ~F~ - κινείται προς τα εμπρός, κατά ένα τετράγωνο στο πλέγμα, προς την κατεύθυνση που βλέπει ή
• ~L~ - στρέφεται κατά ~90~ μοίρες αριστερόστροφα, παραμένοντας στο ίδιο τετράγωνο ή
• ~R~ - στρέφεται κατά ~90~ μοίρες δεξιόστροφα, παραμένοντας στο ίδιο τετράγωνο.

Αφού κάνει αυτές τις κινήσεις, ο Colin στέκεται σε κάποια τελική θέση. Τώρα πρέπει να καταλάβει πού στέκεται. Θα τον βοηθήσετε γράφοντας ένα πρόγραμμα, ώστε να καθορίσει όλες τις πιθανές τελικές θέσεις. Ας υποθέσουμε ότι η αρχική θέση, η τελική θέση και όλες οι ενδιάμεσες θέσεις του Colin βρίσκονται στην πίσω αυλή, αλλά ποτέ σε ένα τετράγωνο που περιέχει ένα εμπόδιο. Μπορείτε επίσης να υποθέσετε ότι ο Colin βλέπει πάντα μια κατεύθυνση που είναι παράλληλη με τις πλευρές της πίσω αυλής (βόρεια, νότια, ανατολικά ή δυτικά).

Η είσοδος ξεκινά με τα ~r~ και ~c~ ~(1 \le r \le 375,\,1 \le c \le 80)~, το καθένα σε ξεχωριστή γραμμή. Ακολουθούν ~r~ γραμμές ~c~ χαρακτήρων, που περιγράφουν την πίσω αυλή: ένας χαρακτήρας τελείας υποδηλώνει ένα τετράγωνο του πλέγματος από το οποίο μπορεί να περάσει ο Colin. Ένας χαρακτήρας ~X~ υποδηλώνει ένα τετράγωνο του πλέγματος με ένα εμπόδιο. Κάτω από το πλέγμα είναι ο αριθμός ~m~ ~(0 \le m \le 30000)~ ακολουθούμενος από ~m~ γραμμές που περιγράφουν τις κινήσεις του Colin. Κάθε γραμμή έχει έναν μόνο χαρακτήρα: ~F~, ~L~ ή ~R~.

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

Παράδειγμα

input

2
4
....
.XX.
3
F
R
F

output

.*..
.XX*