CCC Word Hunt

Στο CCC Κυνήγι Λέξεων, οι λέξεις είναι κρυμμένες σε ένα πλέγμα γραμμάτων. Τα γράμματα μιας κρυμμένης λέξης εμφανίζονται πάντα με τη σειρά σε οριζόντια, κάθετα ή διαγώνια τμήματα γραμμών με έναν από τους δύο τρόπους. Ο ένας τρόπος είναι τα γράμματα μιας λέξης να εμφανίζονται σε ένα τμήμα γραμμής. Ο άλλος τρόπος είναι τα γράμματα μιας λέξης να εμφανίζονται σε ένα τμήμα γραμμής μέχρι κάποιο γράμμα και στη συνέχεια σε ένα δεύτερο τμήμα γραμμής που σχηματίζει ορθή γωνία στο γράμμα αυτό.

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

Είσοδος

Η πρώτη γραμμή εισόδου θα περιέχει μια συμβολοσειρά ~W~ από διακριτά κεφαλαία γράμματα, που αντιπροσωπεύουν τη λέξη που πρόκειται να αναζητήσετε στο πλέγμα. Το μήκος της συμβολοσειράς ~W~ θα είναι τουλάχιστον δύο. Η δεύτερη γραμμή εισόδου θα περιέχει έναν ακέραιο αριθμός ~R\;(1 \le R \le 100)~, όπου ~R~ είναι ο αριθμός των γραμμών του πλέγματος. Η τρίτη γραμμή εισόδου θα περιέχει έναν ακέραιο αριθμό ~C\;(1 \le C \le 100)~, όπου ~C~ είναι ο αριθμός των στηλών του πλέγματος. Η υπόλοιπη είσοδος θα παρέχει τα γράμματα του πλέγματος. Θα αποτελείται από ~R~ γραμμές, όπου κάθε γραµµή θα περιέχει ~C~ κεφαλαία γράµµατα χωρισµένα µε κενά διαστήματα.

Ο ακόλουθος πίνακας δείχνει πώς κατανέμονται οι ~15~ διαθέσιμοι βαθμοί:

Βαθμοί	Τοποθέτηση Λέξης
~2~	Σε ένα οριζόντιο τμήμα.
~2~	Σε ένα οριζόντιο ή κάθετο τμήμα.
~2~	Σε ένα οριζόντιο, κάθετο ή διαγώνιο τμήμα.
~9~	Σε ένα τμήμα ή δύο κάθετα μεταξύ τους τμήματα

Έξοδος

Η έξοδος θα αποτελείται από έναν μη αρνητικό ακέραιο ~H~, που αντιπροσωπεύει τον αριθμό των φορών που η λέξη είναι κρυμμένη στο πλέγμα.

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

input

MENU
5
7
F T R U B L K
P M N A X C U
A E R C N E O
M N E U A R M
M U N E M N S

output

3

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

Η λέξη ~MENU~ είναι κρυμμένη τρεις φορές στο πλέγμα. Μία φορά οριζόντια, μία φορά κάθετα και μία φορά διαγώνια, όπως φαίνεται στην εικόνα. Παρατηρήστε ότι ένα γράμμα μπορεί να χρησιμοποιηθεί περισσότερες από μία φορές.

εικονα

input

NATURE
6
9
N A T S F E G Q N
S A I B M R H F A
C F T J C U C L T
K B H U P T A N U
D P R R R J D I R
I E E K M E G B E

output

4

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

Η λέξη ~NATURE~ είναι κρυμμένη τέσσερις φορές στο πλέγμα. Μία φορά διαγώνια, μία φορά κάθετα και δύο φορές σε κάθετα τμήματα γραμμών.