Minimum Tarp Punctures

The International Consortium of Port Connoisseurs (ICPC) is facing a challenge! The vineyards in the Douro Valley (represented as an interval on the x‐axis) must receive enough rainwater. However, slanted tarps installed above the vineyards, though letting sunlight through, are completely waterproof and divert rain. When rain falls vertically from infinitely high, if it hits a tarp it flows along the tarp toward its lower end and then falls vertically from that endpoint. If a puncture is made on a tarp between the point where the rain hits and the tarp’s lower end, the rain will fall through that puncture instead, giving the ICPC the ability to control from which x‐coordinate the rain resumes its vertical fall.

Your task is to help the ICPC make the minimum number of punctures so that at least one drop of rain that originated directly from above the vineyard (i.e. with an x‐coordinate in the vineyard interval) eventually lands in the vineyard on the ground (the x‐axis). Note that if a vertical drop does not encounter any tarp, it lands directly with the same x–coordinate. However, when a drop meets a tarp without a puncture, it is forced to fall at the tarp’s lower endpoint – which might be outside the vineyard. When puncturing a tarp, you may choose the puncture point arbitrarily along the segment between where the drop first hits the tarp and its lower endpoint. This gives you the opportunity to “steer” the vertical fall by choosing a new x–coordinate from an interval.

Input Geometry: Each tarp is a non–axis–parallel line segment given by its two endpoints (x₁, y₁) and (x₂, y₂). The vineyard is represented by an interval [L,R] on the x–axis.

Note: For legal reasons, at least some of the rain that reaches the vineyard must have originally fallen from directly above the vineyard.

inputFormat

The input begins with a line containing two numbers L and R (L < R), representing the vineyard interval on the x–axis.

The next line contains an integer n (n ≥ 0), the number of tarps.

Then follow n lines; each line contains four real numbers x₁, y₁, x₂, y₂ representing the endpoints of a tarp. The tarps are slanted; neither horizontal nor vertical.

You may assume that 0 ≤ n ≤ 50 and all coordinates have at most 6 digits after the decimal.

outputFormat

Output a single integer: the minimum number of punctures needed so that there exists at least one drop that started from some x in [L,R] and eventually lands on the ground (x–axis) at a point in [L,R].

sample

0 10
0

0