== include(page="template/taskheader" task_id="trapezoid") ==

Poveste şi cerinţă...

Considera doua linii orizontale alese arbitrar. Un trapezoid $T{~i~}$ are doua varfuri situate pe linia superioara si doua situate pe linia inferioara (vezi figura de mai jos). Vom denumi $a{~i~}, b{~i~}, c{~i~}, d{~i~}$ varfurile stanga-sus, dreapta-sus, stanga-jos si dreapta-jos ale trapezoidului $T{~i~}$. O multime de trapezoizi se numeste independenta daca niciunul dintre membrii sai nu se intersecteaza.
 
h2. Cerinta
 
Dandu-se $N$ trapezoizi, aflati cardinalitatea celei mai mari submultimi indepedente de-a sa. De asemenea, trebuie sa aflati si numarul de submultimi independente de cardinal maxim, modulo 30013.

h2. Date de intrare

Fişierul de intrare $trapezoid.in$ ...

Pe prima linie se va afla $N$, numarul de trapezoizi dati. Fiecare din urmatoarele $N$ linii va contine cele 4 numere: $a{~i~}, b{~i~}, c{~i~}, d{~i~}$. Nu vor exista doua trapezoide ce se intersecteaza intr-un singur punct.

h2. Date de ieşire

În fişierul de ieşire $trapezoid.out$ ...

Singura linie a fisierului de iesire va contine doua numere separate prin spatiu: cardialitatea celei mai mari submultimi independente, apoi numarul submultimilor independente de cardinal maxim modulo 30013.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1$ ≤ $N$ ≤ $100.000$
* $1$ ≤ $a{~i~}, b{~i~}, c{~i~}, d{~i~} ≤ 1.000.000.000$
* Pentru un raspuns corect la prima cerinta, veti primi 40% din punctajul testului
* Pentru 40% din teste, $N$ ≤ 5.000

h2. Exemplu
table(example). |_. trapezoid.in |_. trapezoid.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 7
1 3 1 9
4 7 2 8
11 15 4 12
10 12 15 19
16 23 16 22
20 22 13 25
30 31 30 31
| 3 8

|
h3. Explicaţie

...

!problema/trapezoid?trapezoid.png!
 
Atentie, imaginea de mai sus nu este o reprezentare fidela a datelor de intrare. Laturile sus jos au fost mutate pentru vizibilitate.

== include(page="template/taskfooter" task_id="trapezoid") ==