Joy of Flight

Jacob flies a radio-controlled aircraft. Today is windy, so he has to plan the flight in advance. He has a forecast that gives the wind for every second of the flight.

The airspeed of the plane during one second can be any vector of length at most $v_{max}$. If the airspeed during a second is $(v_x, v_y)$ and the wind during that same second is $(w_x, w_y)$, the plane moves by $(v_x + w_x, v_y + w_y)$ in that second.

Jacob has fuel for exactly $k$ seconds. He wants to know whether the plane can get from the start $S$ to the finish $F$ within that time, and if it can, where the plane is at the end of each second.

The first line contains four integers $S_x$, $S_y$, $F_x$, $F_y$, the coordinates of the start and the finish ($-10000 \le S_x, S_y, F_x, F_y \le 10000$).

The second line contains three integers $n$, $k$, $v_{max}$: the number of wind records, the length of the flight in seconds, and the maximum airspeed ($1 \le n, k, v_{max} \le 10000$).

Each of the next $n$ lines contains three integers $t_i$, $w_{x_i}$, $w_{y_i}$. From time $t_i$ on, the wind blows by the vector $(w_{x_i}, w_{y_i})$ each second ($0 = t_1 < t_2 < \dots < t_n < k$, and $\sqrt{w_{x_i}^2 + w_{y_i}^2} \le v_{max}$). The wind during the second that runs from time $j$ to time $j + 1$ is the vector of the last record whose time $t_i$ is at most $j$.

Write $w_j$ for the wind during the $j$-th second, $W = w_1 + w_2 + \dots + w_k$ for the total drift, and $D = F - S - W$ for the displacement the plane has to cover on its own.

If the length of $D$ is greater than $k \cdot v_{max}$, print No on a single line.

Otherwise print Yes on the first line, then the $k$ lines of the flight plan. Print the plan that holds the airspeed constant at $D / k$ for the whole flight, so the position at the end of the $i$-th second is

$P_i = S + \sum_{j=1}^{i} w_j + \frac{i}{k} D$

The $i$-th of those $k$ lines contains the two coordinates of $P_i$, separated by a space, each written with exactly 6 digits after the decimal point. A coordinate that lands exactly halfway between two multiples of $10^{-6}$ is rounded up.

This plan uses airspeed of length $|D| / k$ in every second, so it respects the speed limit whenever any plan does.