Human Error

Ο Justin και ο Donald παίζουν το αγαπημένο τους παιχνίδι: χοροπηδηχτό σκάκι. Πιθανότατα δεν το έχετε ακουστά, αλλά οι κανόνες είναι αρκετά απλοί.

Το ταμπλό είναι ένα ορθογώνιο παραλληλόγραμμο πλέγμα, με κάθε τετράγωνο του ταμπλό να έχει αρχικά ακριβώς ένα πιόνι του παίχτη πάνω του. Τα πιόνια του Justin συμβολίζονται με ~J~ και του Donald με ~D~. Κάθε παίχτης έχει αρχικά τουλάχιστον ένα πιόνι στο πλέγμα.

Το παιχνίδι ξεκινά με τον Justin να παίζει πρώτος. Σε ένα γύρο, ένας παίχτης μπορεί να μετακινήσει ένα από τα πιόνια του για να αιχμαλωτίσει (και έτσι να αφαιρέσει από το ταμπλό) ένα γειτονικό πιόνι (όχι απαραίτητα του αντιπάλου). Ένα πιόνι ~X~ λέγεται ότι είναι γειτονικό στο ~Y~ αν είναι είτε πάνω, κάτω, αριστερά ή δεξιά του ~Y~. Αν μια τέτοια κίνηση δεν μπορεί να γίνει, τότε ο ενεργός παίχτης χάνει.

Σε έναν ιδανικό κόσμο, και ο Justin και ο Donald έχουν τέλεια λογική και είναι ικανοί να διακρίνουν τη βέλτιστη στρατηγική για κάθε ταμπλό. Τότε ίσως μας ενδιέφερε ποιός από τους δύο θα κέρδιζε. Αλλά αυτό δεν θα ήταν πολύ ρεαλιστικό. Πράγματι, όταν παίζουν, ο Justin και ο Donald μπορούν να σκεφτούν μια αρκετά καλή λύση, ακριβώς πόσο καλή είναι καθορίζεται από τους συντελεστές σφάλματός τους, ~J~ και ~D~ αντίστοιχα.

Τυπικά, ο ενεργός παίκτης με συντελεστή σφάλματος \(Α\) επιλέγει πρώτα ένα σύνολο προτάσεων: είτε το σύνολο όλων των πιθανών κινήσεων εάν υπάρχουν \(Α\) ή λιγότερες δυνατές κινήσεις ή κάποιο υποσύνολο μεγέθους \(Α\) από το σύνολο των πιθανών κινήσεων αν έχει περισσότερες από ~A~ πιθανές κινήσεις. Στη συνέχεια, από αυτό το σύνολο προτάσεων, ο παίκτης επιλέγει μια κίνηση τυχαία με ίση πιθανότητα.

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

Η φυσική ερώτηση είναι η εξής: ποιά είναι ακριβώς η πιθανότητα να κερδίσει ο Justin μία παρτίδα χοροπηδηχτό σκάκι, δεδομένου του αρχικού ταμπλό, του ~J~ και του ~D~;

Είσοδος

Η είσοδος θα ξεκινήσει με δύο θετικούς ακέραιους, χωρισμένους με κενό, ~R~, ~C~ (~R~ ~\cdot~ ~C~ ~\le~ ~13~). Στις επόμενες ~R~ γραμμές θα υπάρχουν συμβολοσειρές από ~C~ χαρακτήρες από το σύνολο {~J~, ~D~}, που θα περιγράφουν την αρχική κατάσταση του ταμπλό. Τέλος, θα υπάρχουν δύο ακέραιοι, χωρισμένοι με κενό, ~J~, ~D~ (~1~ ~\le~ ~J~, ~D~ ~\le~ ~13~).

Έξοδος

Εκτυπώστε ένα μόνο πραγματικό αριθμό (float point number) στρογγυλοποιημένο στα ~3~ δεκαδικά σημεία: την πιθανότητα να κερδίσει ο Justin.

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

input

1 3
JJD
3 1

output

0.667

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

Σημειώστε ότι ο Justin έχει ~3~ πιθανές κινήσεις (σημειώστε ότι το _ αντιπροσωπεύει ένα άδειο κελί σε όλες τις παρακάτω εξηγήσεις):

• κινεί το πρώτο του πιόνι δεξιά, αιχμαλωτίζοντας το δεύτερό του πιόνι και εξασφαλίζοντας την ήττα του κάνοντας το ταμπλό να έχει την μορφή _JD

• κινεί το δεύτερό του πιόνι δεξιά, αιχμαλωτίζοντας το πιόνι του Donald και εξασφαλίζει τη νίκη, με το ταμπλό να έχει τη μορφή J_J

• ή κινεί το δεύτερό του πιόνι αριστερά, αιχμαλωτίζοντας το δικό του πιόνι, αλλά αφήνοντας τον Donald να μην μπορεί να κινηθεί, κερδίζοντας έτσι την παρτίδα, με το ταμπλό να έχει τη μορφή J_D

Ξεκάθαρα οι ~2~ τελευταίες περιπτώσεις είναι οι βέλτιστες - αλλά μιας και ο Justin έχει συντελεστή σφάλματος ~3~, υπάρχει πιθανότητα ~1~/~3~ να διαλέξει την επιλογή που θα τον κάνει να χάσει. Άρα η πιθανότητα να νικήσει είναι ~2~/~3~.

input

2 2
JJ
DD
3 1

output

0.000

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

Δεν υπάρχει περίπτωση να κερδίσει ο Justin.

Για να δείτε το γιατί, παρατηρήστε ότι ο Justin έχει ~4~ πιθανές πρώτες κινήσεις:

J_   _J   J_   _J
DD   DD   DJ   JD

Μπορεί να διαλέξει οποιδήποτε υποσύνολο μεγέθους τρία από τις παραπάνω κινήσεις.

Ωστόσο, ο Donald θα διαλέγει πάντα τη βέλτιση κίνησή του. Ανεξάρτητα από την πρώτη κίνηση του Justin, ο Donald θα φύγει από το ταμπλό με έναν από τους παρακάτω σχηματισμούς:

D_   _J   _D   J_
_D   D_   D_   _D

όλοι από τους οποίους θα αναγκάσουν τον Justin να χάσει.