Qanat

A qanat is an irrigation system that delivers water in hot, dry climates. Persian builders developed the technique more than 2000 years ago. In Morocco a qanat is called a khettara, and the southern part of the country still uses them.

The main part of a qanat is a nearly horizontal channel that carries water from an underground source to an outlet near a settlement. A vertical shaft called the mother well runs from the underground source up to the surface of a mountain or a hill. Building such a system costs a great deal, and it cost even more in ancient times, because every bit of excavated dirt has to be carried above ground, either out through the channel outlet or up the mother well. Builders therefore sink one or more extra vertical shafts at chosen points above the horizontal channel. Those shafts have to be dug as well, but they give the crew a shorter route for lifting dirt out of the channel.

Figure 1: The structure of a qanat.

Model the cross-section of a qanat as follows. The channel outlet is at $(0, 0)$, the water source is at $(w, 0)$, and the top of the mother well is at $(w, h)$, with $w > h$. The mountain surface is the straight line from $(0, 0)$ to $(w, h)$.

Figure 2: A simplified model of a qanat cross-section.

Every qanat has the vertical mother well running from the water source to the mountain surface, plus $n$ extra vertical shafts. The channel and all shafts are line segments. Place the $n$ extra shafts so that the total excavation cost is as small as possible. That cost is the sum, over all excavated dirt, of the distance each piece of dirt travels to reach the surface, and the dirt may move by any combination of horizontal and vertical steps. For example, excavating a continuous stretch of dirt that starts at the surface and follows a path of length $\ell$ (turns allowed) costs $\int_0^\ell x\,dx = \frac{1}{2}\ell^2$.

The first line contains three integers $w$, $h$, and $n$ separated by spaces. ($1 \le w \le 10000$, $1 \le h < w$, $1 \le n \le 1000$)

$w$ is the horizontal distance from the water source to the channel outlet, $h$ is the vertical distance from the water source to the mountain surface, and $n$ is the number of vertical shafts dug in addition to the mother well.

On the first line, print the minimum total excavation cost. Then print the $x$-coordinates of the $n$ extra vertical shafts in increasing order, one per line. If $n$ is greater than 10, print only the first 10 coordinates.

Print every value rounded to exactly six digits after the decimal point. The optimal placement is unique, and no shaft lies within 0.001 of the channel outlet or of another shaft.