nori

Pe planeta Aret există un continent de formă dreptunghiulară împărțit în $R \cdot C$ pătrate identice, dispuse alăturat câte $C$ pe fiecare rând și câte $R$ pe fiecare coloană. Fiecare pătrat reprezintă câte o țară. Rândurile sunt numerotate de la $1$ la $R$ de sus în jos, iar coloanele de la $1$ la $C$ de la stânga la dreapta. O țară situată pe rândul $X$ și coloana $Y$ este identificată prin coordonatele $(X, Y)$.

Deasupra continentului circulă $N$ nori, de diferite tipuri, ca în figura $1$, care sunt formați și ei din pătrate identice, iar suprafața unui pătrat acoperă în întregime suprafața unei țări. Norii pot intra pe continent prin vest și se deplasează pe orizontală spre est, sau pot intra pe continent prin nord și se deplasează pe verticală spre sud.

În fiecare oră, norii se deplasează cu câte o poziție în direcția de deplasare, iar atunci când norul părăsește în totalitate suprafața continentului, intră din nou pe continent deasupra aceleași țări acoperite la prima intrare (poziția inițială) și continuă deplasarea. Norii intră pentru prima dată deasupra continentului după un timp de așteptare W și se pot suprapune în timpul deplasării. Un nor se numește ”întreg”, dacă în timpul deplasării, există cel puțin o oră în care norul este situat deasupra continentului și nu depășește marginile continentului.

În exemplul din figura $2$ sunt trei nori, simbolizați prin cifrele $1$, $2$ și $3$. Norul $1$ - de tip $1$ - pătrunde pe continent prin țara $(2, 1)$ după $3$ ore de așteptare, norul $2$ - de tip $3$ - pătrunde prin țara $(4, 1)$ după $0$ ore de așteptare, iar norul $3$ - de tip $5$ - pătrunde prin țara $(1, 3)$ după $1$ oră de așteptare. În acest exemplu este redată poziția fiecărui nor în primele $9$ ore. În țările care nu sunt acoperite de nori cerul este senin, iar în țările peste care se suprapun cel puțin doi nori este furtună.

Cerinţe

Cunoscând numerele naturale $R$, $C$, $N$, coordonatele țării pe unde intră fiecare nor pe continent, tipul acestuia, precum și timpul de așteptare al fiecărui nor la prima intrare pe continent, se cere:

1. Să se determine numărul $A$ al norilor întregi și timpul $B$ minim după care toți norii întregi sunt situați deasupra continentului, fără a depăși marginile acestuia;
2. Cunoscând și un timp $T$, să se determine numărul $S$ de țări care au cerul senin după $T$ ore și numărul $F$ de țări în care este furtună după $T$ ore.

Date de intrare

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

• Pe prima linie, un număr natural $P$ care poate avea doar valorile $1$ sau $2$;
• Pe linia a doua, patru numere naturale $R$, $C$, $N$ și $T$, în această ordine, despărțite prin câte un spațiu, cu semnificația din enunț;
• Pe următoarele $N$ linii se află câte patru numere naturale $X_i$, $Y_i$, $Z_i$ și $W_i$, unde $i \in \{1, 2, 3, \dots, N\}$ în această ordine, despărțite prin câte un spațiu. Numerele $X_i$ și $Y_i$ reprezintă linia și coloana, țării prin care intră norul $i$ pe continent, $Z_i$ reprezintă tipul norului $i$, iar $W_i$ reprezintă timpul de așteptare al norului $i$ la prima intrare deasupra continentului.

Date de ieșire

• Dacă valoarea lui $P$ este $1$, se va rezolva numai cerința $1$) În acest caz, fișierul de ieșire nori.out va conține pe prima linie două numere naturale $A$ și $B$, în această ordine, despărțite prin câte un spațiu. Numărul $A$ reprezintă numărul norilor întregi, iar $B$ este timpul minim determinat;
• Dacă valoarea lui $P$ este $2$, se va rezolva numai cerința $2$). În acest caz, fișierul de ieșire nori.out va conține pe prima linie două numere naturale $S$ și $F$, în această ordine, despărțite printr-un spațiu. Numărul $S$ reprezintă numărul de țări care au cer senin după $T$ ore, iar $F$ reprezintă numărul de țări în care este furtună după $T$ ore.

Restricții și precizări

• $2 \leq R, C \leq 200$;
• $1 \leq N \leq 50$;
• $1 \leq T \leq 2 \ 000 \ 000$;
• $1 \leq Z_i \leq 25$; $Z_i$ este număr impar; $Z_i$ poate fi mai mare decât $R$ sau $C$;
• $0 \leq W_i \leq 200$;
• Pentru cerinta $1$), se garantează că $1 \leq B < 300 \ 000$;
• Pot exista mai mulți nori care intră pe continent prin aceeași țară;
• Niciun nor nu intră pe continent prin țara cu coordonatele $(1, 1)$;
• Dacă $X_i$ = $1$ atunci $2 \leq Y_i \leq C$
• Dacă $Y_i$ = $1$ atunci $2 \leq X_i \leq R$
• Pentru rezolvarea corectă a cerinței $1$. se obține $30\%$ din punctaj, iar pentru cerința $2$. se obține $70\%$ din punctaj.

Exemplul 1

nori.in

1
5 3 3 9
2 1 1 3
4 1 3 0
1 3 5 1

nori.out

2 9

Explicație

Vezi exemplul din figura $2$. Sunt $2$ nori întregi și anume norul $1$ și norul $2$. Cei doi nori sunt situați în întregime deasupra continentului, prima dată după $9$ ore.

Exemplul 2

nori.in

2
5 3 3 9
2 1 1 3
4 1 3 0
1 3 5 1

nori.out

8 2

Explicație

Vezi exemplul din figura $2$. După $T=9$ ore țările cu cer senin sunt la coordonatele:
$(1, 1)$, $(1, 2)$, $(1, 3)$, $(2, 1)$, $(2, 3)$, $(3, 1)$, $(3, 3)$, $(5, 1)$ iar țările în care este furtună sunt la coordonatele: $(4, 3)$ și $(5, 2)$.