题目描述

考虑两条水平的直线，这两条线之间会有 $N$ 个梯形。

如果两个梯形不相交，则称他们在一个独立集内。

您需要求出最大的独立集大小和这种独立集的个数。

输入格式

第一行为一个整数 $N$ 。

接下来 $N$ 行，每行四个整数 $a_i,b_i,c_i,d_i$ ，分别表示第 $i$ 个梯形的左上，右上，左下和右下顶点。

输出格式

仅一行两个整数，表示最大的独立集大小和这种独立集的个数。

由于独立集的个数可能很多，请输出其 $\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

样例说明 1

数据规模与约定

对于 $50\%$ 的数据，保证 $1\le N\le 5\times 10^3$ 。

对于 $100 \%$ 的数据，保证 $1\le N \le 10^5 , 1\le a_i,b_i,c_i,d_i \le 10^9$ ，没有两个梯形具有相同的顶点。

评分方式

如果您只回答对了第一个问题，能得到该测试点 $40\%$ 的分数。

所以，如果您只会第一个问题，也请在第二个问题随便输出一点。

题目来源

Balkan Olympiad in Informatics 2011 Day 2 T3 trapezoid。