Fişierul intrare/ieşire:	trapezoid.in, trapezoid.out	Sursă	BOI 2011
Autor		Adăugată de	Serban Cercelescu •oldatlantian
Timp execuţie pe test	0.5 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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.

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.

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.

Date de ieşire

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.

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

Exemplu

Explicaţie

Atentie, imaginea de mai sus nu este o reprezentare fidela a datelor de intrare. Laturile sus jos au fost mutate pentru vizibilitate.

Cum se trimit solutii?