Rezolvare PBinfo #4641

Domnișoara R este o tânără foarte pasionată de medicină. Aceasta, pregătindu-se constant pentru admiterea la UMF, constată că are un obstacol – Stresu’. Domnișoara R are o casă cu N x M camere, aranjate pe N linii (numerotate de la 1 la N) și M coloane (numerotate de la 1 la M), dintre care B camere sunt inaccesibile (nu este permis accesul în acestea). Vom nota cu [i, j] (1 ≤ i ≤ N, 1 ≤ j ≤ M) camera situată pe linia i și coloana j. Pentru că Universul este neprietenos, vrea să îi pună bețe în roate d-rei. R și astfel îl trimite pe Stresu’ în casa acesteia în camera [X,Y], care este o cameră accesibilă. Stresu’ se poate deplasa în orice cameră adiacentă camerei în care se află (situată pe aceeași linie pe o coloană alăturată sau pe aceeași coloană pe o linie alăturată) sau își poate folosi unul dintre așii din mânecă. Stresu’ dispune de Q ași. Când utilizează asul cu numărul i (1 ≤ i ≤ Q) Stresu’ se poate deplasa din camera [L1i, C1i] în camera [L2i, C2i]. Orice deplasare (utilizând un as sau într-o cameră adiacentă) necesită o secundă și deplasarea nu poate fi efectuată dacă presupune revenirea în ultima cameră care a fost vizitată. Se garantează că dacă există un as în mânecă de la camera [L1,C1] la camera [L2,C2], nu va exista un alt as de la camera [L2,C2] la camera [L1,C1].

Dra. R se află inițial în camera [1, 1]. Când aceasta constată că Stresu’ a intrat în casă, se panichează și urmează un traseu ilustrat printr-un șir de caractere care descrie direcțiile de deplasare:

• L – din camera [i, j] se va deplasa în camera [i, j − 1]
• R – din camera [i, j] se va deplasa în camera [i, j + 1]
• U – din camera [i, j] se va deplasa în camera [i − 1, j]
• D – din camera [i, j] se va deplasa în camera [i + 1, j]

Se garantează că d-ra R nu va trece prin camere inaccesibile. Stresu’ și d-ra R nu pot staționa în camere, fiecare dintre ei trebuie să efectueze o deplasare la fiecare secundă.

Cerința

Știind că scopul lui Stresu’ este să o prindă pe d-ra R, scrieți un program care să determine timpul minim în care Stresu’ poate ajunge în aceeași cameră cu d-ra R.

Date de intrare

Fișierul de intrare drar.in conține pe prima linie numerele N M Q X Y B, reprezentând dimensiunile casei d-rei R, numărul de ași din mâneca lui Stresu’, coordonatele camerei pe unde intră Stresu’, respectiv numărul de camere inaccesibile. Următoarele B linii conțin camerele inaccesibile, câte o cameră pe o linie. Pe următoarele Q linii sunt descriși așii, câte un as pe o linie, sub forma celor 4 numere L1i C1i L2i C2i, (1 ≤ i ≤ Q) cu semnificația din enunț. Pe ultima linie din fișier se va afla șirul de caractere care descrie modul în care se deplasează d-ra R. Numerele scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire drar.out va conține o singură linie pe care va fi scris timpul minim în care Stresu’ poate ajunge în aceeași cameră cu d-ra R sau valoarea −1 dacă acest lucru nu este posibil.

Restricții și precizări

• 1 ≤ N, M ≤ 200
• 1 ≤ X ≤ N, 1 ≤ Y ≤ M
• 0 ≤ Q ≤ 1000
• 0 ≤ B ≤ N x M
• 1 ≤ L1i, L2i ≤ N, 1 ≤ C1i, C2i ≤ M
• 1 ≤ lungimea traseului ≤ 200
• Pentru 10 puncte, X = Y = 1
• Pentru 30 de puncte, 1 ≤ N, M ≤ 6, 0 ≤ Q ≤ 3
• Pentru 30 de puncte, 7 ≤ N, M ≤ 50
• Pentru 30 de puncte, nu există restricții suplimentare.

Exemplu:

drar.in

6 6 4 5 2 5
2 1
4 4
2 4
3 2
2 6
6 4 2 2
3 4 2 3
5 1 2 5
3 5 3 3
RRRRDD

drar.out

6