barlog

Este anul 2019, dar Zmeul-Cel-Rău şi Făt-Frumos luptă în continuare. Zmeul l-a prins pe Făt-Frumos şi l-a închis în una dintre camerele bârlogului său. Un bârlog de zmeu are forma unui tablou bidimensional, în care camerele sunt plasate sub forma a $n$ linii şi $m$ coloane. Vom numerota liniile de la $1$ la $n$, iar coloanele de la $1$ la $m$, astfel că fiecare cameră poate fi identificată prin numărul liniei şi al coloanei pe care se află.
Orice cameră are patru pereţi şi câte o uşă pe fiecare perete prin care poate comunica cu camerele învecinate. Mai exact, camera de pe linia $i$ şi coloana $j$ poate comunica cu camerele $(i-1,j)$, $(i,j+1)$, $(i+1,j)$, $(i,j-1)$ (desigur, dacă acestea există). Fiecare cameră are asociat un cod. Uşile din orice cameră se pot deschide cu o cartelă magnetică. Dacă codul camerei este un subşir al cuvântului memorat pe cartela magnetică, atunci uşile din camera respectivă se vor deschide folosind cartela. Ileana Cosânzeana a reuşit să-i trimită lui Făt-Frumos o cartelă magnetică.

Cerinţă

Scrieţi un program care rezolvă următoarele două cerinţe:

1. determină numărul de camere în care ar putea ajunge Făt-Frumos folosind cartela primită de la Ileana Cosânzeana;
2. determină numărul minim de camere prin care trece Făt-Frumos pentru a ieşi din bârlogul zmeului (adică poate deschide uşa unei camere prin care ajunge în exteriorul bârlogului).

Date de intrare

Fişierul de intrare barlog.in conţine pe prima linie cerinţa $c$ care trebuie să fie rezolvată ($1$ sau $2$). Pe a doua linie se află două numere naturale $n \ m$, reprezentând numărul de linii şi respectiv numărul de coloane ale tabloului care reprezintă bârlogul zmeului. Pe următoarele $n$ linii se află câte $m$ cuvinte, reprezentând în ordine codurile de acces ale camerelor din bârlogul zmeului. Pe ultima linie sunt două numere naturale şi un cuvânt $lin \ col \ cuv$, reprezentând linia şi coloana camerei în care a fost închis Făt-Frumos, precum şi cuvântul înscris pe cartela magnetică primită de Făt-Frumos de la Ileana Cosânzeana. Valorile scrise pe aceeaşi linie sunt separate prin câte-un spaţiu.

Date de ieşire

Fişierul de ieşire barlog.out va conţine o singură linie pe care va fi scris un număr natural determinat conform cerinţei $c$.

Restricții și precizări

• $2 \leq n, m \leq 100$;
• Codurile camerelor şi cuvântul de pe cartelă sunt cuvinte nevide, formate din maxim $20$ de litere mici ale alfabetului englez.
• Pentru datele de test, Făt-Frumos va putea ieşi întotdeauna din bârlogul zmeului.
• Cuvântul $a$ este un subşir al cuvântului $b$ dacă literele din $a$ se găsesc în $b$ în aceeaşi ordine. De exemplu arma este un subşir al cuvântului marama, dar nu şi al cuvântului tamara.
• Pentru teste valorând $40\%$ din punctaj, cerinţa este $1$.

Exemplul 1

barlog.in

1
5 4
ana are mere bune
dana cere pere multe
cra ana vrea pere
dar dan nu are
sunt bune pe care
3 2 caravana

barlog.out

7

Exemplul 2

barlog.in

2
5 4
ana are mere bune
dana cere pere multe
cra ana vrea pere
dar dan nu are
sunt bune pe care
3 2 caravana

barlog.out

2

Explicații

Camerele în care poate intra Făt-Frumos sunt: $(3,2), (3,3), (2,2), (3,1), (4,2), (2,1), (4,1)$
Poate ieşi din bârlog prin camera $(3,1)$.