teren

Lordul John a decis că a venit vremea să însămânțeze terenul său. Terenul a fost împărțit în parcele organizate în $N$ linii, pe fiecare linie fiind câte $N$ parcele pătrate, fiecare cu suprafața de un metru pătrat. Liniile au fost numerotate de sus în jos de la $1$ la $N$, iar coloanele de la stânga la dreapta de la 1 la $N$.

Fiind un aviator pasionat, a folosit avionul său pentru a survola terenul în vederea însămânțării. Când se află în zbor deasupra câte unei parcele, aruncă în aceasta o singură sămânță. Lordul realizează $M$ zboruri deasupra terenului, iar în fiecare astfel de zbor se deplasează în câte o singură direcție, paralelă cu laturile sau cu diagonalele terenului.
Fiecare zbor $i$ (cu $1 \leq i \leq M$ ) este definit printr-un set de patru valori, $LS_i$, $CS_i$, $LF_i$, $CF_i$, unde ($LS_i$, $CS_i$) sunt coordonatele (linia și coloana) primei parcele în care a aruncat o sămânță și ($LF_i$, $CF_i$) sunt coordonatele parcelei în care a aruncat ultima sămânță, în cadrul acestui zbor.

La final, după însămânțare, Lordul John dorește să împrejmuiască cu gard parcelele însămânțate, pentru a le separa de cele rămase neînsămânțate sau de marginea terenului.

Se cunosc $N$, $M$, precum și valorile ($LS_1$, $CS_1$, $LF_1$, $CF_1$), ($LS_2$, $CS_2$, $LF_2$, $CF_2$), $\dots$, ($LS_M$, $CS_M$, $LF_M$, $CF_M$) cu semnificația din enunț.

Cerință

• Determinați numărul semințelor care sunt aruncate.
• Determinați numărul de parcele care sunt însămânțate.
• Determinați lungimea gardului care trebuie să separe suprafețele însămânțate de cele neînsămânțate sau de marginea terenului.

Date de intrare

Fișierul teren.in conține pe prima linie trei numere naturale, $C$, $N$ și $M$, unde $C$ este numărul cerinței care trebuie rezolvată (care poate fi doar $1$, $2$ sau $3$), iar $N$ și $M$ au semnificația din enunț.

Pe următoarele $M$ linii se află câte patru numere naturale, reprezentând seturile de valori care definesc zborurile, în ordinea realizării lor.

Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul teren.out conține numărul determinat pentru cerința $C$.

Restricții și precizări

• $1 \leq N, LS, LF, CS, CF \leq 1 \ 000$.
• $1 \leq M \leq 100 \ 000$

Exemplul 1

teren.in

1 7 6
2 2 2 4
1 3 5 3
1 2 4 5
3 5 6 2
5 4 5 1
7 5 5 7

teren.out

23

Explicație

Se rezolvă cerința $C = 1$.
Figura 1 din enunțul original al problemei teren.Mărește schema ↗

În figura anterioară, primul zbor este marcat de săgeata roșie; se survolează parcelele de la coordonatele $(2, 2)$, $(2, 3)$ și $(2, 4)$; la acest zbor se aruncă $3$ semințe.

Al doilea zbor este marcat de săgeata albastru-deschis; la acest zbor se aruncă $5$ semințe.
În total, în cele $6$ zboruri sunt aruncate $3 + 5 + 4 + 4 + 4 + 3 = 23$ de semințe.

Exemplul 2

teren.in

2 7 6
2 2 2 4
1 3 5 3
1 2 4 5
3 5 6 2
5 4 5 1
7 5 5 7

teren.out

19

Explicație

Se rezolvă cerința $C = 2$. Parcelele însămânțate sunt colorate cu galben:
Figura 2 din enunțul original al problemei teren.Mărește schema ↗

Exemplul 3

teren.in

3 7 6
2 2 2 4
1 3 5 3
1 2 4 5
3 5 6 2
5 4 5 1
7 5 5 7

teren.out

36

Explicație

Se rezolvă cerința $C = 3$. Gardurile folosite sunt marcate cu culoarea roșie, aflate la marginea unor parcele colorate cu galben:
Figura 3 din enunțul original al problemei teren.Mărește schema ↗