[Balkan 2011]trapezoid

时间限制：5s 空间限制：128MB

题目描述

平面上有两条水平直线。现在有一些梯形，其两个顶点都落在上面的直线，另外两个顶点则位于下面的直线（见下图）。ai,bi,ci和di分别表示第i个梯形的左上顶点、右上顶点，左下顶点和右下顶点。若这些梯形的一个子集S中任意两个梯形均不相交，则S被视为是“独立”的。求最大独立集的元素个数（“最大”的意思是元素最多）和不同最大独立集的个数。个数对30013取模。

输入格式

第一行一个整数N，表示梯形的个数。接下来的N行每行四个整数ai,bi,ci和di。任意两个梯形都没有公共顶点。

输出格式

一行用空格分开的两个整数。第一个是最大独立集的元素个数，第二个是不同最大独立集的个数模上30013。

数据规模
1 ≤ N ≤ 100 000
1 ≤ ai, bi, ci, di ≤ 1 000 000 00
如果只有第一个整数是正确的，你将会得到该测试点40%的分数。
40% 的数据有 N ≤ 5000
样例解释
下图并不是样例的精确表示，梯形的上边和下边分别被下移和上移以便于观察。

样例输入

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

提示

题目来源

鸣谢Lyuu