TRAPEZBO - Trapezoid

Consider two arbitrarily chosen horizontal lines. A trapezoid Ti between these lines has two vertices situated on the upper line and the other two vertices on the lower line (see figure below). We will denote by ai, bi, ci and di the upper left, upper right, lower left and respectively lower right vertices of the trapezoid Ti. A subset S of trapezoids is called independent if no two trapezoids from S intersect.

Task

Determine the cardinality of the largest independent set of trapezoids (the largest set means the set with most elements). Also find the count of different independent sets with maximum cardinality. Find this count modulo 30013.

Input

The first line of input contains one integer N – the number of trapezoids. Each of the next N lines contains four integers ai, bi, ci and di. No two trapezoids have a common vertex (corner).

Output

The only line of output should contain two numbers separated by space: firstly, the cardinality of the largest independent set; secondly, the count of different independent sets with maximum cardinality modulo 30013.

Constraints

1 = N = 100 000

1 = ai, bi, ci, di = 1 000 000 000

Example

The picture below is NOT an accurate representation. The trapezoids' top and bottom have been shifted up and down for visibility.

Trapezoid_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

Added by:kipoujr
Date:2012-02-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Balkan Olympiad In Informatics, 2011, Romania

hide comments
2024-06-01 12:47:33
sigma
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.