TRAPEZOI - Hình thang

• Thời gian: 2.0s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

Trong mặt phẳng với hệ trục tọa độ Oxy lấy hai đường thẳng y=y1 và y=y2 (y1>y2).

Cho N hình thang đánh số 1, 2, ..., N, hình thang i có 4 đỉnh là (y1,a _i ),(y1,b _i ),(y2,c _i ),(y2,d _i ) với a _i <b _i và c _i <d _i .

Hai hình thang được gọi là giao nhau nếu tồn tại 1 cạnh của hình thang này và 1 cạnh của hình thang kia có số điểm chung >0.

Một tập các hình thang được gọi là tập độc lập nếu không có hai hình thang nào trong tập giao nhau.

Hai tập các hình thang được gọi là khác nhau nếu tồn tại một hình thang thuộc tập này mà không thuộc tập còn lại.

Yêu cầu

• Tìm kích thước của tập độc lập có kích thước lớn nhất.
• Tính số tập độc lập khác nhau là tập độc lập có kích thước lớn nhất.

Input:

• Dòng 1: Số nguyên N, số hình thang
• Dòng 2:các số nguyên  a _i ,b _i ,c _i ,d _i . (không có hai hình thang nào có chung đỉnh)

Output:

• Một dòng duy nhất ghi 2 số nguyên là kích thước của tập độc lập lớn nhất, số lượng các tập độc lập lớn nhất chia dư cho 30013 .

Giới hạn:

• 1≤ N ≤100 000
• 1≤ a _i , b _i , c _i , d _i ≤ 1000 000 000

Example

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

Output:
3 8

Giải thích:
Hình ảnh minh họa cho test này:



Tập lớn nhất gồm 3 hình thang
Có 8 tập lớn nhất:
(1;4;7) (1;5;7) (1;6;7) (2;4;7) (2;5;7) (2;6;7) (3;5;7) (3;6;7).

• Người up: c_hunter
• Nguồn bài: Balkan OI 2011