Bulletin Board

Interview

Time limit1sMemory limit128 MB

Summary

Given up to 100 axis-aligned rectangles on a board, report the uncovered area, the maximum overlap depth, and the area covered at exactly that depth.

Level: Medium6 of 10
Topics: Geometry, Sorting, Prefix sum, Implementation
Solved: No attempts yet

Problem

The ACM Student Chapter has just been given custody of several school bulletin boards. Several members agreed to clear off the old posters and found posters plastered many layers deep. They made a bet about three quantities: how much of the board area was left clear, what was the greatest depth of posters stacked on top of one another, and how much of the area was covered to that greatest depth. To settle each bet they precisely measured every poster's position as they removed it. Because there are so many posters, they need a program to do the calculations, and that is your job.

Consider a small example: a bulletin board 45 units wide by 40 high holds three posters, one with corners at (10, 10) and (35, 20), another with corners at (20, 25) and (40, 35), and a third with corners at (25, 5) and (30, 30). The total area not covered by any poster is 1300, the maximum number of posters stacked on top of each other is 2, and the total area covered by exactly 2 posters is 75.

Input

The input consists of one to twenty data sets, followed by a line containing only 0. On each line the data consists of blank-separated nonnegative integers.

The first line of a data set contains three integers $n$ $w$ $h$ , where $n$ is the number of posters and $w$ and $h$ are the width and height of the bulletin board. The constraints are $0 < n \le 100$ , $0 < w \le 50000$ , and $0 < h \le 40000$ .

The data set continues with $n$ lines, each describing one poster. Every poster is a rectangle with horizontal and vertical sides. The $x$ and $y$ coordinates are measured from one corner of the bulletin board. Each line contains four integers $xl$ $yl$ $xh$ $yh$ , where $(xl, yl)$ is the corner with the lowest $x$ and $y$ coordinates and $(xh, yh)$ is the diagonally opposite corner with the highest coordinates. Each poster fits on the board, so $0 \le xl < xh \le w$ and $0 \le yl < yh \le h$ .

Output

For each data set print one line containing three integers: the total area of the bulletin board that is not covered by any poster, the maximum depth of posters stacked on top of one another, and the total area covered exactly that maximum number of times.

Caution: an approach that examines every pair of integer coordinates might have to deal with as many as 2 billion coordinate pairs.

Examples1

Example 1

Input

3 45 40
10 10 35 20
20 25 40 35
25 5 30 30
1 20 30
5 5 15 25
2 2000 1000
0 0 1000 1000
1000 0 2000 1000
3 10 10
0 0 10 10
0 0 10 10
0 0 10 10
0

Expected output

1300 2 75
400 1 200
0 1 2000000
0 3 100