La recherche de pierres précieuses est un passe-temps qui consiste à chercher des roches et des pierres précieuses de valeur dans l'environnement naturel. En tant que chercheur de pierres précieuses de niveau national, vous êtes déterminé à trouver la pierre la plus précieuse possible !

Vous avez trouvé une zone de terrain dont la coupe transversale peut être modélisée par un plan euclidien 2D avec le sol sur la ligne $y = 0$. Tout ce qui se trouve sous cette ligne est de la pierre solide, et tout ce qui se trouve au-dessus est de l'air. Enfouies dans la pierre se trouvent $N$ pierres précieuses rares, chacune à une position $(x, y)$ (potentiellement non unique) avec $y < 0$.

Certaines de ces pierres précieuses ont déjà été tracées par d'autres chercheurs, qui ont revendiqué leur découverte en publiant leurs emplacements (tout en laissant les pierres en place). Cela laisse encore quelques pierres précieuses à découvrir pour vous !

Pour trouver réellement les pierres précieuses, vous prévoyez d'utiliser un oscilloscope pour détecter les ondes émises par chaque pierre. Chaque pierre a une fréquence unique qui peut être mesurée à distance ; cependant, cet oscilloscope spécifique a une particularité : chaque fois qu'il est utilisé, il n'enregistre que la fréquence émise par la pierre la plus proche, en utilisant la distance euclidienne. En cas d'égalité, il choisit arbitrairement une fréquence émise par l'une des pierres les plus proches.

Figure G.1 : Une illustration de l'Exemple 1. Les icônes de pierres précieuses sous terre représentent les pierres déjà découvertes, et les points à la surface indiquent vos relevés d'oscilloscope.

Vous venez d'utiliser l'oscilloscope $N$ fois à divers emplacements uniques $(x_j, 0)$ à la surface de la Terre. Vous avez enregistré ces emplacements ainsi que la fréquence $f_j$ détectée par l'oscilloscope à cet emplacement. Fait intéressant, vous avez remarqué que la fréquence de chaque pierre précieuse apparaît exactement une fois dans vos enregistrements.

Parmi les pierres qui n'ont pas encore été découvertes par d'autres chercheurs, vous aimeriez trouver la plus précieuse. Et bien sûr, plus la pierre est profonde, plus elle est précieuse !

Une configuration plausible des pierres précieuses est un placement de chaque pierre non découverte sur le plan euclidien 2D qui satisfait aux conditions suivantes :

• chaque pierre précieuse est souterraine ($y < 0$) ;
• pour chaque relevé d'oscilloscope de fréquence $f_j$ à l'emplacement $(x_j, 0)$, aucune pierre précieuse n'est plus proche de $(x_j, 0)$ en distance euclidienne que la pierre avec la fréquence $f_j$.

Vous souhaitez calculer, pour chaque pierre précieuse non encore découverte, la coordonnée $y$ la plus profonde possible (la plus négative) de cette pierre parmi toutes les configurations plausibles de pierres précieuses.

Entrée

La première ligne contient deux entiers séparés par un espace $N$ ($2 \le N \le 10^5$) et $K$ ($1 \le K \le N - 1$) : le nombre de pierres précieuses enfouies (et de relevés d'oscilloscope) et le nombre de ces pierres qui ont déjà été découvertes par d'autres chercheurs, respectivement.

Chacune des $K$ lignes suivantes contient trois entiers séparés par un espace $x_i$ ($|x_i| \le 10^6$), $y_i$ ($-10^6 \le y_i < 0$), et $f_i$ ($1 \le f_i \le N$), décrivant l'emplacement et la fréquence d'une pierre précieuse qui a déjà été découverte. Il est possible que deux pierres précieuses ou plus occupent le même emplacement. Il est garanti que les valeurs $f_i$ sont uniques.

Enfin, chacune des $N$ dernières lignes contient deux entiers séparés par un espace $x_j$ ($|x_j| \le 10^6$) et $f_j$ ($1 \le f_j \le N$), décrivant un relevé d'oscilloscope. Il est garanti que les valeurs $x_j$ sont uniques, qu'elles sont listées par ordre croissant, et que chaque pierre précieuse (découverte ou non) a exactement un relevé d'oscilloscope. Il est également garanti qu'il existe au moins une configuration plausible de pierres précieuses.

Sortie

Pour chacune des $N - K$ pierres précieuses non découvertes, imprimez une ligne avec un entier et un nombre réel négatif : la fréquence $f_\ell$ de la pierre précieuse et la coordonnée $y$ la plus profonde (la plus négative) possible $y_\ell$ de cette pierre parmi toutes les configurations plausibles des pierres précieuses. Il peut être prouvé que cette coordonnée $y$ la plus profonde possible existe pour chaque pierre précieuse non découverte et est négative et finie.

Vous pouvez imprimer ces lignes dans n'importe quel ordre. Votre réponse sera acceptée si chaque valeur de profondeur que vous attribuez à une pierre précieuse non découverte diffère de la solution du juge par une erreur relative ou absolue d'au plus $10^{-5}$.

Exemples

Entrée 1

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

Sortie 1

2 -7.615773
3 -3.162278
5 -5.830952

Entrée 2

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

Sortie 2

3 -3.605551