The ACM Student Chapter has just been given custody of a number of school bulletin boards. Several members agreed to clear off the old posters. They found posters plastered many levels deep. They made a bet about how much area was left clear, what was the greatest depth of posters on top of each other, and how much of the area was covered to this greatest depth. To determine each bet's winner, they made very accurate measurements of all the poster positions as they removed them. Because of the large number of posters, they now need a program to do the calculations. That is your job.

A simple illustration is shown above: a bulletin board 45 units wide by 40 high, with three posters, one with corners at coordinates (10, 10) and (35, 20), another with corners at (20, 25) and (40, 35), and the last with corners at (25, 5) and (30, 30). The total area not covered by any poster is 1300. The maximum number of posters on top of each other is 2. The total area covered by exactly 2 posters is 75.

Input

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

The first line of a dataset contains integers n w h, where n is the number of posters on the bulletin board, w and h are the width and height of the bulletin board. Constraints are 0 < n ≤ 100; 0 < w ≤ 50000; 0 < h ≤ 40000.

The dataset ends with n lines, each describing the location of one poster. Each poster is rectangular and has horizontal and vertical sides. The x and y coordinates are measured from one corner of the bulletin board. Each line contains four numbers xl yl xh and yh, where xl and yl, are the lowest values of the x and y coordinates in one corner of the poster and xh and yh are the highest values in the diagonally opposite corner. Each poster fits on the bulletin board, so 0 ≤ xl < xh ≤ w, and 0 ≤ yl < yh ≤ h.

Output

There is one line of output for each data set containing three integers, the total area of the bulletin board that is not covered by any poster, the maximum depth of posters on top of each other, and the total area covered this maximum number of times.

Caution: An approach examining every pair of integer coordinates might need to deal with 2 billion coordinate pairs.

Example

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

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

---

hide comments

	:D: 2017-01-07 01:24:44 There few issues here. First of all, I just assumed 'w', 'h' and all coordinates fit into 32-bit integers. It can be solved efficiently with those constrains. Next, data seems to hold (0 <= xl < xh) and (0 <= yl < yh) inequalities, but we have cases where (xh > w) and (yh > h). Looking at how my code logic worked in those cases, it basically expanded 'w' and 'h' to fit all posters, but newer lowered those values: w = max(w, max{all xh}) h = max(h, max{all yh})
	Shaka Shadows: 2010-07-16 14:39:10 The input doesn't match what the text says: I had to increase the MAXH value to 100000 while the text says just 40000. Can the problemsetter please modify the text above in order to make it match the test data. Last edit: 2010-07-16 14:43:27
	Shaka Shadows: 2010-07-16 13:58:31 Is there something wrong with test cases?? I'm getting RE but I'm pretty sure about my algorithm. Even I have tested my code with official test data and everything is OK.
	Tony Beta Lambda: 2009-10-04 12:40:40 I strongly doubt (again) that the test cases are incorrect. I submitted standard program of the contest but it got RE. PS: I don't know why my (previous) post is removed. I did not spam. Edit by Blue Mary: How do you know that the standard program of that contest is absolutely correct? Okay, okay, but as you can see, so many SPOJ users tried but failed, including some experienced coders. Besides, I assume the standard program could get TLE, but not RE anyway. In my opinion, better it is to check your test data than to quarrel here. I'm sure there are cases where x > w or y > h. Last edit: 2010-06-24 08:46:33
	ahmed saad : 2009-07-22 02:48:03 there is a figure missing