题目描述

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

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

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

由于独立集的个数可能很多，请输出其 $\bmod\ 30013$ 的值。

输入格式

第一行为一个整数 $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

提示

样例解释

下面这个图不怎么准确，但是应该够用：

数据范围及限制

• 对于 $50\%$ 的数据，保证 $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$，没有两个梯形具有相同的顶点。

SPJ 计分标准

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

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

说明

本题译自 Balkan Olympiad in Informatics 2011 Day 2 T3 trapezoid。