P6744 [BalkanOI 2011] trapezoid

Consider two horizontal straight lines. Between these two lines there are $N$ trapezoids. If two trapezoids do not intersect, then we say they are in the same independent set. You need to find the maximum size of an independent set and the number of such independent sets. Since the number of independent sets may be very large, output its value $\bmod\ 30013$.

The first line contains an integer $N$. The next $N$ lines each contain four integers $a_i, b_i, c_i, d_i$, representing the top-left, top-right, bottom-left, and bottom-right vertices of the $i$-th trapezoid, respectively.

Output a single line with two integers: the maximum size of an independent set and the number of such independent sets. Since the number of independent sets may be very large, output its value $\bmod\ 30013$.

#### Sample Explanation The following picture is not very accurate, but it should be enough:  #### Constraints - For $50\%$ of the testdata, it is guaranteed that $N \le 5 \times 10^3$. - For $100\%$ of the testdata, it is guaranteed that $1 \le N \le 10^5$, $1 \le a_i, b_i, c_i, d_i \le 10^9$, and no two trapezoids share the same vertex. #### SPJ Scoring Rules If you only answer the first question correctly, you will get $40\%$ of the score for that test point. So, if you can only solve the first question, please also output something random for the second question. #### Note This problem is translated from [Balkan Olympiad in Informatics 2011](http://www.boi2011.ro/boi2011/) [Day 2](http://www.boi2011.ro/boi2011/?pagina=probleme) [T3 trapezoid](http://www.boi2011.ro/resurse/tasks/trapezoid.pdf)。 Translated by ChatGPT 5