Cerința

Rică se joacă în fiecare seară The MazeRunnerVladVersion, joc pe care îl vom numi pentru simplitatea problemei MR. Jocul constă în găsirea unei căi de scăpare dintr-un labirint care conține:

• ziduri prin care Rică nu va putea să treacă;
• zero sau mai multe teleporturi cu ajutorul cărora deplasarea între două puncte precizate p1(x1, y1) și p2(x2, y2) se face într-un minut, dacă se doreşte acest lucru;
• zone libere, trecerea din zona curentă într-o zonă învecinată se poate face pe direcția celor patru puncte cardinale. Deplasarea se va face într-un minut.

Rică pleacă din colțul stânga-sus al labirintului și doreşte să ajungă în colțul dreapta-jos.

El știe că are o teză în ziua următoare, așa că vă cere ajutorul vouă, programatorilor, și vă roagă să aflați timpul minim în care poate să ajungă din colțul stânga-sus în colțul dreapta-jos al labirintului.

Date de intrare

Fișierul de intrare mr.in conține:

• numărul L de linii și numărul C de coloane pentru harta labirintului, separate printr-un spațiu
• pe următoarele L linii se vor găsi C valori de -1 (reprezentând zid) sau 0 separate printr-un spațiu
• pe linia L+2 se va găsi numărul de teleporturi T
• pe fiecare dintre următoarele T linii se vor găsi câte patru numere de forma: L1 C1 L2 C2 separate printr-un spațiu, reprezentând poziţiile de pe hartă ale teleporturilor. Rică poate să aleagă să se teleporteze din poziția L1 C1 în poziția L2 C2.

Date de ieșire

Fișierul de ieșire mr.out va conține pe prima linie timpul minim necesar lui Rică pentru a parcurge labirintul.

Restricții și precizări

• 2 ≤ n, m ≤ 100
• 0 ≤ T ≤ 100
• Pentru fiecare set de date de intrare există soluție.
• Pentru 50% din teste nu există teleporturi.

Exemplul 1

mr.in

5 5
 0  0 -1 0 0 
 0 -1  0 0 0 
 0  0  0 0 0
-1 -1  0 0 0
 0  0  0 0 0
 0

mr.out

8

Explicație

Un drum minim posibil este:

(1, 1) → (2, 1) → (3, 1) → (3, 2) → (3, 3) → (4, 3) → (5, 3) → (5, 4) → (5, 5)

Exemplul 2

mr.in

5 6	
 0  0  0  0 -1  0
 0  0 -1 -1  0  0
-1  0  0  0 -1  0
-1  0 -1  0  0  0
-1 -1 -1  0  0  0
2
2 2 4 5
4 2 2 5

mr.out

5

Explicație

Un drum minim posibil este:

(1, 1) → (1, 2) → (2, 2) → (4, 5) → (4, 6) → (5, 6).

Între pozițiile (2,2) și (4,5) s-a utilizat primul teleport.