EscapeLight

Labirintul EscapeLight este reprezentat printr-o matrice de dimensiuni $N \cdot M$, unde fiecare celulă reprezintă o cameră. Fiecare cameră poate fi de unul dintre următoarele tipuri:

• Tipul $0$: cameră cu bec stins,
• Tipul $1$: cameră cu bec aprins,
• Tipul $2$: cameră fără bec,
• Tipul $3$: cameră echipată cu un întrerupător.

Camerele de tip $3$ sunt conectate la becuri din alte camere de tip 0 sau 1. Când cineva intră într-o cameră cu întrerupător, are posibilitatea să treacă mai departe fără a-l act, iona sau să-l apese. Apăsarea întrerupătorului inversează starea tuturor becurilor conectate (becurile aprinse se sting, iar cele stinse se aprind).
Andrei pornește dintr-o cameră aflată la coordonatele $(x_{start}, y_{start})$ și trebuie să ajungă la o cameră situată la $(x_{stop}, y_{stop})$, deplasându-se exclusiv prin camere luminoase (adică, camerele în care becul este aprins). Scopul este de a găsi drumul de distanță minimă, măsurat în numărul de camere parcurse, ținând cont de posibilitatea de a utiliza întrerupătoarele pentru a schimba starea luminilor.

Date de intrare

Prima linie a fișierului de intrare conține două numere întregi $N$ și $M$, reprezentând numărul de linii și coloane ale labirintului.
Următoarele $N$ linii conțin câte $M$ numere, separate prin spații, fiecare reprezentând tipul camerei:

• $0$ — cameră cu bec stins,
• $1$ — cameră cu bec aprins,
• $2$ — cameră fără bec,
• $3$ — cameră cu întrerupător.

A doua secțiune a inputului este formată dintr-o linie care conține patru numere întregi: $x_{start}, y_{start}, x_{stop}$ și $y_{stop}$, reprezentând coordonatele camerei de start și ale camerei de destinație.

Următoarea linie conține un număr întreg $K$, reprezentând numărul de conexiuni și un număr întreg $P$, reprezentând numărul de camere de tip $3$.

Fiecare din următoarele $K$ linii conține patru numere întregi: $x_{switch}, y_{switch}, x_{light}, y_{light}$, indicând că întrerupătorul din camera de coordonate $(x_{switch}, y_{switch})$ este conectat la becul din camera de coordonate $(x_{light}, y_{light})$.

Date de ieșire

Programul va afișa un singur număr, reprezentând numărul minim de camere parcurse pentru a ajunge de la poziția de start la poziția de destinație, ținând cont de posibilitatea de a utiliza întrerupătoarele.

Restricții și precizări

• $1 \leq N, M \leq 150$
• $0 \leq K \leq 10^5$
• $0 \leq P \leq 10$
• $1 \leq x_{start}, x_{stop} \leq N, 1 \leq y_{start}, y_{stop} \leq M$
• Pentru fiecare conexiune: $1 \leq x_{switch}, x_{light} \leq N, 1 \leq y_{switch}, y_{light} \leq M$
• Conexiunile se vor face doar între camerele de tip $3$ (întrerupătoare) și camerele de tip $0$ sau $1$.
• Camerele de tip $3$ sunt considerate mereu luminoase.
• Se garantează existența unei soluții.

Exemplu

escapelight.in

3 3
1 0 2
3 1 0
2 0 1
1 1 3 3
2 1
2 1 1 2
2 1 3 2

escapelight.out

5

Explicație

În exemplul de mai sus, labirintul are $3$ linii și $3$ coloane. Andrei începe din camera $(1, 1)$, care este luminată (tipul $1$), iar destinația este camera $(3, 3)$, tot luminată (tipul $1$). Deoarece unele camere inițial sunt întunecate, Andrei trebuie să utilizeze întrerupătorul din camera $(2, 1)$ (tipul $3$) pentru a aprinde becurile din camerele $(1, 2)$ și $(3, 2)$, astfel încât să îi permită accesul la o cale validă. Drumul minim găsit are $5$ camere parcurse.