Trapezoids

Consider two parallel horizontal lines. A trapezoid $T_i$ lies between these two lines, with two of its vertices on the upper line and the other two on the lower line. Denote the four vertices of $T_i$ by the $x$-coordinates $a_i$ (upper left), $b_i$ (upper right), $c_i$ (lower left), and $d_i$ (lower right). Thus its top edge spans the interval $[a_i, b_i]$ and its bottom edge spans $[c_i, d_i]$.

Two trapezoids are said to intersect if they share at least one point. A subset $S$ of the trapezoids is called independent if no two trapezoids in $S$ intersect.

Two trapezoids $T_i$ and $T_j$ do not intersect exactly when one lies entirely to the left of the other on both lines; that is, $T_i$ is to the left of $T_j$ and the two do not intersect if and only if $b_i < a_j$ and $d_i < c_j$.

Determine the size of the largest independent set of trapezoids. Also determine how many different independent sets of that maximum size exist, modulo $30013$.

The first line contains a single integer $N$, the number of trapezoids. Each of the next $N$ lines contains four integers $a_i$, $b_i$, $c_i$, and $d_i$. No two trapezoids share a common vertex (corner).

Print two numbers separated by a space on a single line: first, the size of the largest independent set; then, the number of different independent sets of maximum size, modulo $30013$.

• $1 \le N \le 100,000$
• $1 \le a_i, b_i, c_i, d_i \le 1,000,000,000$

The picture below is not drawn to scale. The tops and bottoms of the trapezoids have been shifted up and down for visibility.