Trader

Într-un vast deșert, transpus ca o matrice de dimensiuni $n \times m$, negustorii se aventurează bazându-se pe reguli prestabilite.

Fiecare își începe călătoria dintr-un loc anume, marcat prin coordonatele $(x, y)$, și urmează o direcție inițială (N, S, E, sau W). Acesta continuă să se deplaseze drept până când dă de o piață. Aceste piețe, dispersate prin deșert, redirecționează parcursul negustorilor. Definite de coordonate $(x, y)$ și o direcție specifică (N, S, E, sau W), ele reconfigurează traiectoria negustorului la intersecție.

Această interacțiune poate fie să-l ghideze către marginea matricei, indicând finalul călătoriei, fie să-l introducă într-un loop de deplasare.
Un loop de deplasare se referă la situația în care traiectoria unui negustor devine predictibilă și se repetă fără sfârșit. Mai precis, după un șir de mișcări, negustorul ajunge să repete o secvență de pași, revenind periodic la aceleași coordonate și direcție.

Cerință

Cerința problemei este următoarea: „Măsurați distanța parcursă de fiecare negustor înainte de a fi prins într-un loop de deplasare, precum și dimensiunea secvenței repetate, dacă există.”.

Aici sau în secțiunea „Atașamente” din lateral puteți găsi un program C++ care implementează această problemă, dar conține câteva bug-uri. Sarcina voastră este să reparați programul.

Date de intrare

Pe prima linie se citesc $n$ și $m$, cu semnificațiile din enunț.

Pe a doua linie se citește $n_{piete}$, reprezentând numărul de piețe care schimbă direcția negustorilor.

Pe a treia linie se citește $n_{negustori}$, reprezentând numărul de negustori pentru care vrem să aflăm răspunsul.

Pe fiecare din următoarele $n_{piete}$ linii se află coordonatele unei piețe în matrice.

Pe fiecare din următoarele $n_{negustori}$ linii se află coordonatele de start a unui negustor și direcția specifică a acestuia.

Date de ieșire

Pe fiecare linie se afișează două numere $d$ și $l$ — distanța parcursă de negustor care nu face parte din loop, respectiv lungimea loop-ului. Negustorii se iau în ordinea în care apar în fișierul de intrare.

Dacă nu există loop, $d$ va fi distanța parcursă până la ieșirea din matrice și $l$ va fi $0$.

Restricții și precizări

• $1 \le n, m \le 500$
• $0 \le n_{piete} \le n \cdot m$
• $0 \le n_{negustori} \le n \cdot m$
• Coordonatele piețelor si ale negustorilor sunt indecși care încep de la $1$.
• Un negustor nu va porni niciodată direct dintr-o piață.

Exemplul 1

stdin

6 6
2
1
1 2 S
6 2 E
1 6 W

stdout

14 0

Explicație

Negustorul se află inițial la coordonatele $(1, 6)$ și are direcția de deplasare spre stânga.

Negustorul merge $4$ pătrățele la stânga pană la piața de coordonate $(1, 2)$.
Apoi, $5$ pătrățele în jos, până la piața de coordonate $(6, 2)$.
Apoi, $4$ pătrățele la dreapta, până iese din matrice.

Acesta nu intră în loop, deci lungimea loop-ului este $0$.

Exemplul 2

stdin

7 7
10
2
1 7 S
5 7 W
5 1 N
1 1 E
2 2 E
2 4 S
6 4 E
6 6 N
4 6 W
4 2 N
1 2 E
1 2 S

stdout

0 20
1 16

Explicație

Primul negustor este reprezentat în imaginea de mai jos cu verde, iar al doilea cu albastru.

Primul negustor se află deja într-un loop de lungime $20$, determinat de primele $4$ piețe.
Al doilea negustor merge o pătrățică în jos până intră într-un loop de lungime $16$, determinat de ultimele $6$ piețe.