Drar

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 \cdot 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 \leq i \leq N, 1 \leq j \leq 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 \leq i \leq Q$) Stresu’ se poate deplasa din camera $[L1_i, C1_i]$ în camera $[L2_i, C2_i]$. 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ță

Ș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 $L1_i \ C1_i \ L2_i \ C2_i$, ($1 \leq i \leq 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 \leq N, M \leq 200$
• $1 \leq X \leq N, 1 \leq Y \leq M$
• $0 \leq Q \leq 1 \ 000$
• $0 \leq B \leq N \cdot M$
• $1 \leq L1i, L2i \leq N, 1 \leq C1_i, C2_i \leq M$
• $1 \leq$ lungimea traseului $\leq 200$

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