RoboThieves

Ένα ρομπότ έχει κλέψει θησαυρό από ένα εργοστάσιο και πρέπει να δραπετεύσει χωρίς να το πιάσουν. Το εργοστάσιο μπορεί να μοντελοποιηθεί με ένα πλέγμα ~N~ επί ~M~, στο οποίο το ρομπότ μπορεί να κινείται πάνω, κάτω, αριστερά ή δεξιά.

Κάθε κελί του πλέγματος είναι είτε άδειο, είτε ένας τοίχος, είτε μια κάμερα, είτε ένας μεταφορέας, είτε η αρχική θέση του ρομπότ. Το ρομπότ μπορεί να περπατήσει μόνο σε κενά κελιά (συμβολίζονται με ~\;.\;~) ή σε μεταφορείς. Η πρώτη σειρά, η τελευταία σειρά, η πρώτη στήλη και η τελευταία στήλη του πλέγματος αποτελούνται από τοίχους (συμβολίζονται με ~W~), και μπορεί να υπάρχουν τοίχοι και σε άλλα κελιά.

Οι μεταφορείς αναγκάζουν το ρομπότ να κινειθεί προς μια συγκεκριμένη κατεύθυνση, που συμβολίζεται με ~L~, ~R~, ~U~, ~D~ για αριστερά, δεξιά, πάνω και κάτω αντίστοιχα. Το ρομπότ δεν μπορεί να κινηθεί μόνο του όταν βρίσκεται σε έναν μεταφορέα. Είναι δυνατόν το ρομπότ να κολλήσει για πάντα σε μεταφορείς.

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

Το ρομπότ βρίσκεται αρχικά στο κελί που συμβολίζεται με ~S~. Η έξοδος θα μπορούσε να είναι σε οποιοδήποτε από τα κενά κελιά. Για κάθε κενό κελί, προσδιορίστε τον ελάχιστο αριθμό βημάτων που χρειάζεται το ρομπότ για να μετακινηθεί εκεί χωρίς να "πιαστεί", ή προσδιορίστε ότι είναι αδύνατο να μετακινηθεί εκεί. Ένα βήμα σημαίνει το ρομπότ να μετακινηθεί μία φορά, προς τα πάνω, προς τα κάτω, αριστερά ή δεξιά. Η μετακίνηση από τον μεταφορέα δεν μετράει ως βήμα.

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει δύο ακέραιους αριθμούς ~N~ και ~M\;(4 \le N,\;M \le 100)~. Οι επόμενες ~N~ γραμμές της εισόδου θα περιέχουν ~M~ χαρακτήρες η καθεμιά, καθένας από τους οποίους θα είναι ένας από τους οκτώ χαρακτήρες ~W~,~\;.\;~, ~C~, ~S~, ~L~, ~R~, ~U~, ή ~D~.

Θα υπάρχει ακριβώς ένας χαρακτήρας ~S~ και τουλάχιστον ένας χαρακτήρας ~\;.\;~ . Ο πρώτος και ο τελευταίος χαρακτήρας της κάθε γραμμής και στήλης θα είναι ~W~.

Για ~5~ από τους ~15~ διαθέσιμους βαθμούς, δεν θα υπάρχουν κάμερες ή μεταφορείς.

Για επιπλέον ~5~ από τους ~15~ διαθέσιμους βαθμούς, δεν θα υπάρχουν μεταφορείς.

Έξοδος

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

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

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

input

4 5
WWWWW
W.W.W
WWS.W
WWWWW

output

-1
2
1

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

Το ρομπότ δεν μπορεί να μετακινηθεί στο επάνω αριστερό κενό κελί επειδή εμποδίζεται από τοίχους.

Το πάνω δεξί άδειο κελί μπορεί να το φτάσει σε ~2~ βήματα και το κάτω δεξί άδειο κελί μπορεί να το φτάσει σε ~1~ βήμα.

input

5 7
WWWWWWW
WD.L.RW
W.WCU.W
WWW.S.W
WWWWWWW

output

2
1
3
-1
-1
1

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

Το άδειο κελί που βρίσκεται ακριβώς αριστερά του ρομπότ είναι ορατό από την κάμερα, οπότε το ρομπότ δεν μπορεί να μετακινηθεί εκεί.

Το άδειο κελί ακριβώς κάτω από τον μεταφορέα ~R~ είναι επίσης ορατό από την κάμερα, καθώς οι μεταφορείς δεν εμποδίζουν το οπτικό πεδίο των καμερών.

Παρατηρήστε ότι το ρομπότ μπορεί να χρησιμοποιήσει τους μεταφορείς ~U~ και ~L~ για να αποφύγει τον εντοπισμό του από την κάμερα.

Εάν το ρομπότ μετακινηθεί στον μεταφορέα ~R~, θα κολλήσει εκεί για πάντα.