Radio-Controlled Aircraft Flight Planning

Jacob enjoys flying his radio-controlled aircraft. Today the weather is quite windy, and he must carefully plan his flight. He has a detailed weather forecast giving the wind speed and direction for every second of his planned flight. The aircraft can achieve an airspeed of up to \(v_{\max}\) units per second in any direction. When the plane chooses an airspeed vector \((v_x, v_y)\) and at that second the wind is blowing at \((w_x, w_y)\), the plane's position is updated by \((v_x+w_x,\; v_y+w_y)\) in that second.

Jacob has enough fuel for exactly \(k\) seconds and wants to know if it is possible for his plane to fly from the starting point \((0,0)\) to the target point in exactly \(k\) seconds. If it is possible, he also needs a concrete flight plan: the position of the plane after each second of flight. Otherwise, he should report that the flight is impossible.

Note on controls: At each second, Jacob chooses an airspeed vector \(\vec{v} = (v_x,v_y)\) satisfying \(\|\vec{v}\| \le v_{\max}\). The wind vector at second \(i\) is given as \((w_{x,i}, w_{y,i})\), and the plane then moves by \(\vec{v}+ (w_{x,i}, w_{y,i})\). The overall displacement due to the airspeed must sum to the difference between the target and the net wind effect.

The required condition for the existence of a flight plan is that if \(\vec{D} = (x_{target}, y_{target}) - \sum_{i=1}^{k} (w_{x,i}, w_{y,i})\), then \(\|\vec{D}\|\le k \cdot v_{\max}\). If this condition is met, a valid sequence of control vectors exists.

inputFormat

The input is given in the following format:

k v_max
x_target y_target
w_x1 w_y1
w_x2 w_y2
... 
w_xk w_yk

Where:

• k is the number of seconds (fuel available).
• v_max is the maximum airspeed the plane can achieve (per second).
• x_target and y_target specify the coordinates of the target point.
• Each of the next k lines contains two integers representing the wind vector \((w_x, w_y)\) at that second.

outputFormat

If it is possible to reach the target exactly in \(k\) seconds, print Yes on the first line, followed by \(k\) lines. The \(i\)th of these lines should contain two real numbers representing the coordinates of the plane after the \(i\)th second. You may output any valid flight plan and answers with a relative or absolute error of up to 10^-6 are accepted.

If it is impossible to reach the target, just print No.

sample

3 10
5 5
0 0
0 0
0 0

Yes
1.666666667 1.666666667
3.333333333 3.333333333
5.000000000 5.000000000