== include(page="template/taskheader" task_id="kdrum") ==

Laura este pasionata de plimbarile prin parc. Fiind totusi o activitate lipsita de originalitate, ea si-a propus ca plimbarile ei sa urmeze un plan mai nastrusnic. Pentru a va ajuta, ea a reprezentat parcul sub forma unei matrici cu $N$ linii si $M$ coloane. Pentru fiecare zona din parc, ea i-a atribuit un numar natural pozitiv dupa criterii numai de ea stiute. Zonele prin care nu poate trece le-a marcat cu $0$. Acum ea se afla in pozitia $x1$ $y1$ si doreste sa ajunga la pozitia $x2$ $y2$ astfel incat produsul numerelor de pe drum sa fie divizibil cu un numar $K$. Pentru ca este frig afara, ea doreste sa stie care este lungimea minima a unui astfel de drum. Cum dorintele ei sunt porunci, voi trebuie sa o ajutati.

Laura este pasionata plimbarile prin parc. Fiind totusi o activitate lipsita de originalitate, ea si-a propus ca plimbarile ei sa urmeze un plan mai nastrusnic. Pentru a va ajuta, ea a reprezentat parcul sub forma unei matrici cu $N$ linii si $M$ coloane. Pentru fiecare zona din parc, ea i-a atribuit un numar natural dupa criterii numai de ea stiute. Zonele prin care nu poate trece le-a marcat cu $-1$. Acum ea se afla in pozitia $x1$ $y1$ si doreste sa ajunga la pozitia $x2$ $y2$ astfel incat produsul numerelor de pe drum sa fie divizibil cu un numar $K$. Pentru ca este frig afara, ea doreste sa stie care este lungimea minima a unui astfel de drum. Cum dorintele ei sunt porunci, voi trebuie sa o ajutati.

h2. Date de intrare

Pe prima linie a fisierului de intrare $kdrum.in$ se afla $3$ numere intregi despartie prin spatiu: $N M K$. Pe urmatoarea linie se gasesc $4$ numere intregi $x1 y1$ $x2 y2$. Urmatoarele $N$ linii vor avea cate $M$ numere despartite prin spatiu, simbolizand schema parcului.

Pe prima linie a fisierului de intrare $kdrum.in$ se afla $3$ numere intregi despartie prin spatiu: $N M K$. Pe urmatoarea linie se gasesc $4$ numere intregi $x1 y1 x2 y2$. Urmatoarele $N$ linii vor avea cate $M$ numere despartite prin spatiu, simbolizand schema parcului.

h2. Date de ieşire

h2. Restricţii

* $1 ≤ N ≤ 50$
* $1 ≤ M ≤ 50$
* $1 ≤ K ≤ 12 000$
* Elementele matricii sunt numere intregi cuprinse in intervalul $[0, 100 000]$.
* Se garanteaza ca pozitiile de start si de final sunt valide.
* Se garanteaza ca exista cel putin un drum valid de la pozitia de start la destinatie.
* In $20%$ din teste, $K = 1$.
* Pentru $50%$ din teste, $1 ≤ K ≤ 200$.
* Deplasarea se face in $4$ directii: sus, jos, stanga, dreapta.
* Laura trebuie sa se deplaseze intr-o casuta vecina in fiecare moment de timp.
* Drumul Laurei poate trece de mai multe ori prin aceeasi pozitie, caz in care trebuie considerata de mai multe ori valoarea din acea zona.

* $1 ≤ N ≤ 200$
* $1 ≤ M ≤ 200$
* $1 ≤ K ≤ 100 000 000$
* Pentru $40%$ din teste, $1 ≤ K ≤ 500$.

h2. Exemplu
table(example). |_. kdrum.in |_. kdrum.out |

| 3 3 6
1 1 3 3
1 3 5
1 0 2
6 1 1
| 5

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

Cele doua solutii posibile sunt:
 
$*1* 3 5$
$*1* 0 2$
$*6 1 1*$
 
sau
 
$*1 3 5*$
$1 0 *2*$
$6 1 *1*$
 
 
Prima solutie are produsul numerelor de pe drum $6$, in timp ce a doua are produsul $30$. Ambele numere sunt divizibile cu $6$.

...

== include(page="template/taskfooter" task_id="kdrum") ==

3633