Description

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$.

Input Format

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 Format

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$.

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

Hint

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 Day 2 T3 trapezoid。

Translated by ChatGPT 5