사다리꼴

시간 제한1초메모리 제한128 MB

요약

두 직선 사이 사다리꼴 중 서로 겹치지 않는 최대 집합 크기와 그 경우의 수를 30013으로 나눈 나머지를 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 정렬, 세그먼트 트리
정답자: 아직 제출이 없습니다

문제

평행한 두 수평선을 생각하자. 사다리꼴 $T_i$ 는 이 두 직선 사이에 놓이며, 두 꼭짓점은 위쪽 직선 위에, 나머지 두 꼭짓점은 아래쪽 직선 위에 있다. $T_i$ 의 네 꼭짓점을 각각 $a_i$ (위 왼쪽), $b_i$ (위 오른쪽), $c_i$ (아래 왼쪽), $d_i$ (아래 오른쪽)의 $x$ 좌표로 나타낸다. 즉 위쪽 변은 구간 $[a_i, b_i]$ 를, 아래쪽 변은 구간 $[c_i, d_i]$ 를 차지한다.

두 사다리꼴이 한 점이라도 공유하면 서로 교차한다고 한다. 사다리꼴들의 부분집합 $S$ 안의 어떤 두 사다리꼴도 교차하지 않으면 $S$ 를 독립집합이라 한다.

두 사다리꼴 $T_i$ 와 $T_j$ 가 교차하지 않는다는 것은 한쪽이 두 직선 모두에서 다른 쪽의 완전히 왼쪽에 있다는 뜻이다. 즉 $b_i < a_j$ 이고 $d_i < c_j$ 이면 $T_i$ 가 $T_j$ 의 왼쪽에 있으며 둘은 교차하지 않는다.

원소가 가장 많은 독립집합의 크기를 구하라. 또한 그 최대 크기를 갖는 서로 다른 독립집합의 개수를 $30013$ 으로 나눈 나머지를 구하라.

입력

첫째 줄에 사다리꼴의 개수 $N$ 이 주어진다. 다음 $N$ 개의 줄에는 각 줄마다 네 정수 $a_i$ , $b_i$ , $c_i$ , $d_i$ 가 주어진다. 어떤 두 사다리꼴도 공통된 꼭짓점(모서리)을 갖지 않는다.

출력

한 줄에 두 수를 공백으로 구분하여 출력한다. 먼저 가장 큰 독립집합의 크기를, 그다음 최대 크기를 갖는 서로 다른 독립집합의 개수를 $30013$ 으로 나눈 나머지를 출력한다.

제한

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

힌트

아래 그림은 정확한 축척이 아니다. 보기 쉽도록 사다리꼴의 위·아래 변을 위아래로 벌려 그렸다.

예제3

예제 1

입력

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

예제 2
입력
```
1
1 2 1 2
```
예상 출력
```
1 1
```
예제 3
입력
```
2
1 2 1 2
3 4 3 4
```
예상 출력
```
2 1
```