Origin of Life

Το "παιχνίδι της ζωής" (the Game of Life) του Conway, δεν είναι στ'αλήθεια ένα παιχνίδι, αλλά ένα κυτταρικό αυτόματο (cellular automaton) - μια σειρά από κανόνες που περιγράφουν αλληλεπιδράσεις μεταξύ γειτονικών κελιών πάνω σε ένα πλέγμα. Στο δικό μας παιχνίδι, έχουμε ένα ορθογώνιο πλέγμα κελιών ~ n\times m~ διαστάσεων, που θα αναπαρίσταται απο τις ακέραιες συντεταγμένες ~(x,\;y)~.

Το παιχνίδι εξελίσσεται μέσα από μια σειρά βημάτων; σε κάθε βήμα μια νέα γενιά (generation) υπολογίζεται από την τρέχουσα γενιά. Το παιχνίδι ξεκινά με την πρώτη γενιά (first generation). Σε οποιαδήποτε δεδομένη γενιά, την οποία θα ονομάσουμε τρέχουσα γενιά, κάθε κελί είναι είτε ζωντανό (live) είτε νεκρό (dead). Στην επόμενη γενιά, η κατάσταση κάθε κελιού μπορεί να αλλάξει, ανάλογα με την κατάσταση των άμεσων γειτόνων του στην τρέχουσα γενιά. Δύο ξεχωριστά κελιά ~(x_{1}, \;y_{1})~ και ~(x_{2}, \;y_{2})~, είναι άμεσοι γείτονες εάν είναι οριζόντια, κάθετα, ή διαγώνια κοντινά, δηλαδή αν ικανοποιούν τη συνθήκη ~ \left| x_{1} - x_{2} \right| \le 1~ και ~ \left| y_{1} - y_{2} \right| \le 1~. Κάθε κελί που δεν βρίσκεται πάνω στο όριο του πλέγματος έχει οκτώ άμεσους γείτονες.

Υπάρχουν τρεις ακέραιες παράμετροι ~(a,\;b,\;c)~ που επηρεάζουν το παιχνίδι. Οι κανόνες του παιχνιδιού είναι:

• Εάν ένα ζωντανό κελί έχει λιγότερους από ~a~ ζωντανούς γείτονες στην τρέχουσα γενιά, πεθαίνει από μοναξιά.
• Έτσι, θα είναι νεκρό στην επόμενη γενιά.
• Εάν ένα ζωντανό κελί έχει περισσότερους από ~b~ ζωντανούς γείτονες στην τρέχουσα γενιά, πεθαίνει από υπερπληθυσμό.
• Έτσι, θα είναι νεκρό στην επόμενη γενιά.
• Εάν ένα νεκρό κελί έχει περισσότερους από ~c~ ζωντανούς γείτονες στην τρέχουσα γενιά, τότε ξαναγεννιέται.
• Δηλαδή είναι ζωντανό στην επόμενη γενιά.
• Διαφορετικά, η κατάσταση ενός κελιού παραμένει αμετάβλητη από την τρέχουσα γενιά στην επόμενη.

Αυτή η διαδικασία συνεχίζεται επ' αόριστον. Τελικά, μια γενιά μπορεί να επαναληφθεί, περίπτωση στην οποία η ζωή συνεχίζεται για πάντα. Ή μπορεί όλα τα κελιά να πεθάνουν. Με όμοιο τρόπο, αν εξερευνήσουμε προηγούμενες γενιές που μπορεί να οδήγησαν στην τρέχουσα, μπορεί να βρούμε μία που να είναι σίγουρα η πρώτη γενιά, γιατί δεν θα μπορούσε ακολουθώντας τους κανόνες να έχει δημιουργηθεί από κάποια άλλη προηγούμενη. Μια τέτοια γενιά είναι γνωστή ως Κήπος της Εδέμ (a Garden of Eden).

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

Είσοδος

Υπάρχουν ~m\;+ \;1~ γραμμές συνολικά στην είσοδο. Η πρώτη γραμμή θα περιέχει τις παραμέτρους του παιχνιδιού, πέντε ακέραιους αριθμούς ~m,\; n,\; a,\; b,\; c~ χωρισμένους με κόμμα, όπου ~1 \le m \le 4~, ~1 \le n \le 5~, ~1 \le a < b \le 8~, ~1 \le c \le 8~. Κάθεμια από τις επόμενες ~m~ γραμμές, περιέχει μια ακολουθία από ~n~ χαρακτήρες representing a row of the current generation. Στην ακολουθία, ο αστερίσκος ("~*~") δηλώνει την κατάσταση ζωντανό (live) ενώ η τελεία ("~\;.\;~") δηλώνει την κατάσταση νεκρό (dead).

Παράδειγμα

input

4 5 2 3 2
.****
.****
.****
.****

output

2

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

Ας υποθέσουμε ότι το παράδειγμα της εισόδου είναι η τρέχουσα γενιά. Μια πιθανή προηγούμενη γενιά είναι:

**.**
..*.*
....*
*****

Η παραπάνω γενιά μπορεί να προέλθει από την ακόλουθη προηγούμενη γενιά:

.****
**.*.
*****
*..*.

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