Slikar

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

Ο χάρτης του Μαγεμένου Δάσους αποτελείται από ~R~ γραμμές και ~C~ στήλες. Τα κενά πεδία αντιπροσωπεύονται από '.' χαρακτήρες, πλημμυρισμένα πεδία από '*' και πέτρες από '~X~'. Επιπλέον, αντιπροσωπεύεται η φωλιά του Κάστορα από το 'D' και ο Ζωγράφος και οι τρεις μικροί σκαντζόχοιροι εμφανίζονται ως '~S~'.

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

Γράψτε ένα πρόγραμμα που, δεδομένου ενός χάρτη του Μαγεμένου Δάσους, που θα παράγει το συντομότερο χρόνο που χρειάζεται για να φτάσουν με ασφάλεια ο Ζωγράφος και οι τρεις σκαντζόχοιροι στη φωλιά του Κάστορα.

Σημείωση: Ο Ζωγράφος και οι τρεις μικροί σκαντζόχοιροι δεν μπορούν να μετακινηθούν σε ένα χωράφι που πρόκειται να πλημμύρισει (στο ίδιο λεπτό).

Είσοδος

Η πρώτη γραμμή εισόδου θα περιέχει δύο ακέραιους αριθμούς, ~R~ και ~C~, μικρότερους ή ίσους με ~50~.
Οι ακόλουθες ~R~ γραμμές θα περιέχουν η καθεμία ~C~ χαρακτήρες ~('.', '*', 'X', 'D'~ ή ~'S')~. Ο χάρτης θα περιέχει ακριβώς ένα χαρακτήρα '~D~' και ακριβώς ένα χαρακτήρα '~S~'.

Έξοδος

Εκτυπώστε τον συντομότερο δυνατό χρόνο που χρειάζονται ο Ζωγράφος και οι τρεις μικροί σκαντζόχοιρους για να φτάσουν με ασφάλεια στη φωλιά του Κάστορα. Εάν αυτό είναι αδύνατο, εκτυπωτε τη λέξη "KAKTUS" σε μια γραμμή από μόνη της.

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

input

3 3
D.*
...
.S.

output

3

input

3 3
D.*
...
..S

output

KAKTUS

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

Το καλύτερο που μπορούν να κάνουν είναι να πάνε κατά μήκος του κάτω συνόρου και μετα του αριστερού συνόρου, και να πλημμυρίσουν ένα λεπτό πριν φτάσουν τη φωλιά.

input

3 6
D...*.
.X.X..
....S.

output

6