22219번 - Rectangles 스페셜 저지다국어

문제

There are given N rectangles on the plane. Rectangle sides are parallel to coordinate axis. These rectangles may overlap, coincide or be drawn inside one another. Their vertices have non-negative integer coordinates and x coordinates do not exceed x_max and y coordinates do not exceed y_max.

A segment is started in the point A(0, 0) and ended in point B. The coordinates of the point B (the other end of the segment) satisfy the following conditions:

• The coordinates of B are integer numbers;
• The point B belongs either to the segment [(0, y_max), (x_max, y_max)] or to the segment [(x_max, 0), (x_max, y_max)];

The segment AB might cross rectangles (we assume that crossing takes place even if only one rectangle vertex is crossed).

Write a program to find a point B for which the segment AB crosses as many rectangles as possible.

Example with 8 rectangles. The segment AB crosses 5 of them.

입력

The first line of the input contains three integers: x_max, y_max (0 < x_max, y_max ≤ 10⁹) and N (1 ≤ N ≤ 10000). Each of the following N lines contains four integers: coordinates of the bottom left corner x_bl and y_bl and coordinates of the top right corner x_tr and y_tr. Neighbouring numbers are separated by single space character.

출력

On the first and only line of the output three integer numbers should be written. First – the maximum number of crossed rectangles followed x and y coordinates of point B. Neighbouring numbers must be separated by single space character.

If there are several solutions, find any one of them.

제한

힌트

Another possible solution is 5 22 11