Trapezoids

Time limit1sMemory limit128 MB

Summary

Pick the most pairwise disjoint trapezoids between two lines and count those optimal sets modulo 30013.

Level: Medium7 of 10
Topics: Dynamic programming, Sorting, Segment tree
Solved: No attempts yet

Problem

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

Input

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

Output

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

Constraints

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

Hint

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

Examples3

Example 1

Input

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

Expected output

3 8

Example 2
Input
```
1
1 2 1 2
```
Expected output
```
1 1
```
Example 3
Input
```
2
1 2 1 2
3 4 3 4
```
Expected output
```
2 1
```