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

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.

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 maximale, modulo 30013.

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

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.

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") ==