Your car is out of gas, and you want to get home as quickly as possible! Fortunately, your home is at the bottom of a hill and you (in your car) are at the top of it. Unfortunately, there is a car in front of you, and you can't move past it. Fortunately, your brakes are working and they are very powerful.
You start at the top of the hill with speed 0 m/s at time 0 seconds. Gravity is pulling your car down the hill with a constant acceleration. At any time, you can use your brakes to reduce your speed, or temporarily reduce your acceleration, by any amount.
How quickly can you reach your home if you use your brakes in the best possible way?
The first line of the input gives the number of test cases, T. T test cases follow. The first line of each test case contains three spaceseparated numbers: a realvalued number D, the distance in meters to your home down the hill; and two integers, N and A. The distance D will be given in exactly 6 decimal places.
N lines follow, each of which contains two spaceseparated, realvalued numbers: a time t_{i} in seconds, and a position x_{i} in meters. The t_{i} and x_{i} values will be given in exactly 6 decimal places.
One line follows, with A spaceseparated, realvalued numbers a_{i}, which are accelerations in m/s^{2}
. The accelerations will be given in exactly 2 decimal places.
The other car's position is specified by the (t_{i}, x_{i}) pairs. The car's position at time t_{i} seconds is x_{i} meters measured from the top of the hill (i.e. your initial position). The car travels at constant speed between time t_{i} and t_{i+1}. The positions and times will both be given in increasing order, with t_{0}=0.
For example, if t_{5}=10, x_{5}=20, t_{6}=20, x_{6}=40, then 10 seconds after the start, the other car is 20 meters down the hill; 15 seconds after the start, the other car is 30 meters down the hill; and 20 seconds after the start, the other car is 40 meters down the hill.
For each test case, output one line containing "Case #c:", where c is the case number (starting from 1). Then output A lines, the i^{th} of which contains the minimum number of seconds it takes you to reach your home if your acceleration down the hill due to gravity is a_{i}, and you use your brakes in the best possible way. Answers within an absolute or relative error of 10^{6} of the correct answer will be accepted. There should be no blank lines in the output.
Position and Acceleration: An object with a constant acceleration a m/s^{2}
and starting speed of v_{0} m/s
will move a distance of v_{0}*t + 0.5*a*t^{2} after t
seconds.
2 m/s^{2}
with an initial speed of 0 m/s
, and the other car is stopped at x=1, it will take exactly 1 second to reach the other car.
The other car: You may never pass the other car, which means that at no time shall your distance down the hill be greater than that of the other car. It may be equal. The cars should be considered as point masses.
Output values: You can print as many decimal places as you like in the output. We will read and compare your answers with ours, and at that time we will be using 10^{6} as a threshold for inaccuracy. So 25, 25.0 and 25.000000 are the same from our perspective. Trailing zeros after the decimal point does not matter.
1 ≤ T ≤ 20.
1.0 ≤ D ≤ 10^{4}.
1.0 ≤ a_{i} ≤ 9.81.
0.0 ≤ t_{i} ≤ 10^{5}.
0.0 ≤ x_{i} ≤ 10^{5}.
t_{i} < t_{i+1}.
x_{i} < x_{i+1}.
t_{0} = 0
x_{N1} ≥ D.
1 ≤ N ≤ 2.
1 ≤ A ≤ 10.
1 ≤ N ≤ 2000.
1 ≤ A ≤ 250.
Input 
Output 
3

Case #1:

Points  Correct  Attempted 

10pt  467  762 
27pt  73  250 