Obdĺžniky 2

V rovine je nakreslených $n$ obdĺžnikov. Strany každého obdĺžnika sú rovnobežné so súradnicovými osami.

Vrcholy každého obdĺžnika majú celočíselné súradnice. Tvojou úlohou je vypočítať obsah ich zjednotenia.

V tejto verzii úlohy platia nasledovné obmedzenia:

Obdĺžnikov je nanajvýš $3 000$.
Všetky súradnice ich vrcholov ležia v uzavretom intervale $[0, 10^9]$.

No ďakujem pekne. Pre toľkoto obdĺžnikov už vykresľovanie do poľa asi stíhať nebude. Potrebovali by sme pole zhruba rozmerov $6 000 \times 6 000$, teda asi $36$ miliónov políčok. Takéto pole čo len raz celé prejsť už môže trvať tak 0.1 sekundy... a my doň potrebujeme vykresliť $3 000$ obdĺžnikov. Tadiaľ cesta nevedie.

Namiesto toho si predstav, že sme zvislé strany všetkých obdĺžnikov predĺžili na priamky. Rovina sa nám tým rozpadne na niekoľko zvislých pásov. Koľko najviac ich bude? Na to, aby si vyriešil(a) túto úlohu, ti stačí spracovať každý zvislý pás zvlášť – teda zvlášť pre každý zvislý pás určiť, aký je obsah zjednotenia toho, čo v ňom leží. Musíš však vymyslieť, ako to spraviť dostatočne efektívne.

Vstup

Na prvom riadku je $n$ - počet obdĺžnikov.

Nasleduje $n$ riadkov, každý popisujúci jeden obdĺžnik. Popis obdĺžnika má tvar x1 y1 x2 y2, kde (x1, y1) a (x2, y2) sú celočíselné súradnice dvoch protiľahlých vrcholov obdĺžnika. Platí, že $0 \leq x_1 < x_2 \leq 10^9$ a $0 \leq y_1 < y_2 \leq 10^9$.

Výstup

Jeden riadok obsahujúci jedno číslo - obsah zjednotenia obdĺžnikov.

Príklady

Vstup

2
7 7 9 9
10 8 13 10

Výstup

Prvý obdĺžnik má rozmery $2 \times 2$ a druhý $3 \times 2$. Keďže sa neprekrývajú, obsah ich zjednotenia je $4+6 = 10$.

Vstup

2
7 7 9 9
8 8 11 10

Výstup

Tie isté dva obdĺžniky, ale teraz sme jeden posunuli aby sa prekrývali. Obsah zjednotenia tým klesol.

Vstup

Výstup

    +---+---+---+
    |           |
    +---+---+---+
        |   |
+---+---+---+
|       |   |
+   +---+   +
|   |   |   |
+   +---+---+
|           |
+---+---+---+