Description

$\emph{Rockhounding}$ is the hobby of searching for valuable rocks and gemstones in the natural environment. As a national-level rockhound yourself, you're determined to find the most valuable gem possible!

You've found an area of land whose cross section can be modeled by a 2D Euclidean plane with the ground at the line $y = 0$. Everything below this line is solid stone, and everything above is air. Buried within the stone are $N$ rare gemstones, each at a (potentially non-unique) $(x, y)$ location with $y < 0$.

Some of these gemstones have already been traced by other rockhounds, who have claimed their discovery by publishing their locations (while leaving the stones themselves in place). That still leaves some gemstones for you to find!

To actually find gemstones, you plan to use an $\emph{oscilloscope}$ to detect waveforms emitted by each gem. Each gem has a unique frequency that can be measured from a distance; however, this specific oscilloscope has a quirk in that each time it is used, it only records the frequency emitted by the $\textbf{closest gem}$, using Euclidean distance. In the case of a tie, it arbitrarily picks a frequency emitted by one of the closest gems.

:::align{center}

An illustration of Sample Input 1. Gem icons underground represent previously discovered gemstones, and points on the surface indicate your oscilloscope readings. :::

You've just used the oscilloscope $N$ times at various $\textbf{unique}$ locations $(x_j, 0)$ on the surface of the Earth. You recorded these locations along with the frequency $f_j$ detected by the oscilloscope at that location. Interestingly enough, you've noticed that the frequency of $\textbf{every gemstone appears exactly once}$ in your records.

Of the gems that haven't yet been discovered by other rockhounds, you'd like to find the most valuable one. And of course, the deeper the gem, the more valuable!

A $\emph{plausible configuration}$ of the gemstones is a placement of each undiscovered gemstone on the 2D Euclidean plane that satisfies the following conditions:

• every gemstone is underground ($y < 0$);
• for every oscilloscope reading of frequency $f_j$ at location $(x_j,0)$, no gemstone is closer to $(x_j,0)$ in Euclidean distance than the gemstone with frequency $f_j$.

You wish to calculate, for each yet-undiscovered gemstone, the deepest possible (most negative) $y$-coordinate of that gem among all plausible configurations of gemstones.

Input Format

The first line contains two space-separated integers $N$ $(2 \le N \le 10^5)$ and $K$ $(1 \le K \le N - 1)$: the number of buried gemstones (and oscilloscope readings) and number of those gemstones that have already been discovered by other rockhounds, respectively.

Each of the next $K$ lines contains three space-separated integers $x_i$ $(|x_i| \le 10^6)$, $y_i$ $(-10^6 \le y_i < 0)$, and $f_i$ $(1 \le f_i \le N)$, describing the location and frequency of a gemstone that has already been discovered. It is possible that two or more gemstones occupy the same location. It is guaranteed that the $f_i$ values are unique.

Finally, each of the last $N$ lines contains two space-separated integers $x_j$ $(|x_j| \le 10^6)$ and $f_j$ $(1 \le f_j \le N)$, describing an oscilloscope reading. It is guaranteed that the $x_j$ values are unique, that they are listed in increasing order, and that every gemstone (discovered and undiscovered) has exactly one oscilloscope reading. It is also guaranteed that there is at least one plausible configuration of gemstones.

Output Format

For each of the $N-K$ undiscovered gemstones, print a line with an integer and a negative real number: the frequency $f_\ell$ of the gemstone and the deepest (most negative) possible $y$-coordinate $y_\ell$ of that gemstone among all plausible configurations of the gemstones. It can be proved that this deepest possible $y$-coordinate exists for every undiscovered gemstone and is negative and finite.

You may print these lines in any order.

Your answer will be accepted if each depth value you assign to an undiscovered gemstone differs from the judge solution by relative or absolute error at most $10^{-5}$.

5 2
7 -3 4
2 -3 1
1 1
3 3
9 4
12 5
14 2

2 -7.615773
3 -3.162278
5 -5.830952

3 2
3 -3 1
3 -3 2
0 1
2 2
5 3

3 -3.605551