La búsqueda de rocas (rockhounding) es el pasatiempo de buscar rocas y piedras preciosas valiosas en el entorno natural. Como buscador de rocas de nivel nacional, ¡estás decidido a encontrar la gema más valiosa posible!

Has encontrado un área de terreno cuya sección transversal puede modelarse mediante un plano euclidiano 2D con el suelo en la línea $y = 0$. Todo lo que está debajo de esta línea es piedra sólida, y todo lo que está arriba es aire. Enterradas dentro de la piedra hay $N$ piedras preciosas raras, cada una en una ubicación $(x, y)$ (potencialmente no única) con $y < 0$.

Algunas de estas piedras preciosas ya han sido rastreadas por otros buscadores, quienes han reclamado su descubrimiento publicando sus ubicaciones (dejando las piedras en su lugar). ¡Eso todavía deja algunas piedras preciosas para que tú las encuentres!

Para encontrar realmente las piedras preciosas, planeas usar un osciloscopio para detectar las formas de onda emitidas por cada gema. Cada gema tiene una frecuencia única que puede medirse desde la distancia; sin embargo, este osciloscopio específico tiene la peculiaridad de que cada vez que se usa, solo registra la frecuencia emitida por la gema más cercana, utilizando la distancia euclidiana. En caso de empate, elige arbitrariamente una frecuencia emitida por una de las gemas más cercanas.

Figura G.1: Una ilustración de la Entrada de ejemplo 1. Los iconos de gemas bajo tierra representan piedras preciosas descubiertas previamente, y los puntos en la superficie indican tus lecturas del osciloscopio.

Acabas de usar el osciloscopio $N$ veces en varias ubicaciones únicas $(x_j, 0)$ en la superficie de la Tierra. Registraste estas ubicaciones junto con la frecuencia $f_j$ detectada por el osciloscopio en esa ubicación. Curiosamente, has notado que la frecuencia de cada piedra preciosa aparece exactamente una vez en tus registros.

De las gemas que aún no han sido descubiertas por otros buscadores, te gustaría encontrar la más valiosa. Y, por supuesto, ¡cuanto más profunda sea la gema, más valiosa es!

Una configuración plausible de las piedras preciosas es una colocación de cada gema no descubierta en el plano euclidiano 2D que satisface las siguientes condiciones:

• cada piedra preciosa está bajo tierra ($y < 0$);
• para cada lectura del osciloscopio de frecuencia $f_j$ en la ubicación $(x_j, 0)$, ninguna piedra preciosa está más cerca de $(x_j, 0)$ en distancia euclidiana que la piedra preciosa con frecuencia $f_j$.

Deseas calcular, para cada piedra preciosa aún no descubierta, la coordenada $y$ más profunda posible (más negativa) de esa gema entre todas las configuraciones plausibles de piedras preciosas.

Entrada

La primera línea contiene dos enteros separados por espacios $N$ ($2 \le N \le 10^5$) y $K$ ($1 \le K \le N - 1$): el número de piedras preciosas enterradas (y lecturas del osciloscopio) y el número de esas piedras preciosas que ya han sido descubiertas por otros buscadores, respectivamente.

Cada una de las siguientes $K$ líneas contiene tres enteros separados por espacios $x_i$ ($|x_i| \le 10^6$), $y_i$ ($-10^6 \le y_i < 0$) y $f_i$ ($1 \le f_i \le N$), que describen la ubicación y la frecuencia de una piedra preciosa que ya ha sido descubierta. Es posible que dos o más piedras preciosas ocupen la misma ubicación. Se garantiza que los valores de $f_i$ son únicos.

Finalmente, cada una de las últimas $N$ líneas contiene dos enteros separados por espacios $x_j$ ($|x_j| \le 10^6$) y $f_j$ ($1 \le f_j \le N$), que describen una lectura del osciloscopio. Se garantiza que los valores de $x_j$ son únicos, que están listados en orden creciente y que cada piedra preciosa (descubierta y no descubierta) tiene exactamente una lectura del osciloscopio. También se garantiza que existe al menos una configuración plausible de piedras preciosas.

Salida

Para cada una de las $N - K$ piedras preciosas no descubiertas, imprime una línea con un entero y un número real negativo: la frecuencia $f_\ell$ de la piedra preciosa y la coordenada $y$ más profunda (más negativa) posible $y_\ell$ de esa piedra preciosa entre todas las configuraciones plausibles de las piedras preciosas. Se puede demostrar que esta coordenada $y$ más profunda posible existe para cada piedra preciosa no descubierta y es negativa y finita.

Puedes imprimir estas líneas en cualquier orden. Tu respuesta será aceptada si cada valor de profundidad que asignes a una piedra preciosa no descubierta difiere de la solución del juez por un error relativo o absoluto de como máximo $10^{-5}$.

Ejemplos

Entrada 1

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

Salida 1

2 -7.615773
3 -3.162278
5 -5.830952

Entrada 2

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

Salida 2

3 -3.605551