Rectangles

Time limit1sMemory limit512 MB

Summary

Find the integer point B on the top or right edge so that segment AB from the origin crosses the most of N axis-parallel rectangles.

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

Problem

There are N rectangles on the plane. Their sides are parallel to the coordinate axes. The rectangles may overlap, coincide, or lie inside one another. Their vertices have non-negative integer coordinates, where x coordinates do not exceed $x_{max}$ and y coordinates do not exceed $y_{max}$ .

A segment starts at $A(0, 0)$ and ends at point $B$ . The coordinates of $B$ satisfy these conditions:

$B$ has integer coordinates.
$B$ lies on the segment $[(0, y_{max}), (x_{max}, y_{max})]$ or on the segment $[(x_{max}, 0), (x_{max}, y_{max})]$ .

Segment $AB$ crosses a rectangle even if it touches only one of its vertices.

Find a point $B$ for which segment $AB$ crosses as many rectangles as possible.

The figure shows 8 rectangles. Segment $AB$ crosses 5 of them.

Input

The first line contains three integers $x_{max}$ , $y_{max}$ ( $0 < x_{max}, y_{max} \le 10^9$ ) and $N$ ( $1 \le N \le 10000$ ). Each of the following N lines contains four integers $x_{bl}$ , $y_{bl}$ , $x_{tr}$ , $y_{tr}$ , the coordinates of the bottom left corner and the top right corner of a rectangle. Adjacent numbers are separated by a single space.

Output

Print one line with three integers. The first is the maximum number of rectangles crossed by segment $AB$ . The second and third are the x and y coordinates of point $B$ . If several answers exist, print any of them.

Hint

Another possible answer is 5 22 11.

Examples1

Example 1

Input

22 14 8
1 8 7 11
18 10 20 12
17 1 19 7
12 2 16 3
16 7 19 9
8 4 12 11
7 4 9 6
10 5 11 6

Expected output

5 22 12