암석 채집(Rockhounding)은 자연환경에서 가치 있는 암석과 보석을 찾는 취미입니다. 국가대표급 암석 채집가인 당신은 가능한 가장 가치 있는 보석을 찾기로 결심했습니다!

당신은 지면을 $y = 0$인 직선으로 하는 2차원 유클리드 평면으로 모델링할 수 있는 토지를 발견했습니다. 이 직선 아래는 모두 단단한 암석이고, 위는 공기입니다. 암석 내부에는 $N$개의 희귀 보석이 묻혀 있으며, 각 보석은 $y < 0$인 위치 $(x, y)$에 존재합니다(위치는 중복될 수 있습니다).

이 보석 중 일부는 이미 다른 암석 채집가들에 의해 추적되었으며, 그들은 보석의 위치를 공개하여 발견 사실을 알렸습니다(보석 자체는 그대로 두었습니다). 하지만 여전히 당신이 찾아야 할 보석들이 남아 있습니다!

실제로 보석을 찾기 위해 당신은 오실로스코프를 사용하여 각 보석에서 방출되는 파형을 감지할 계획입니다. 각 보석은 거리와 상관없이 측정할 수 있는 고유한 주파수를 가지고 있습니다. 하지만 이 특정 오실로스코프에는 사용할 때마다 유클리드 거리를 기준으로 가장 가까운 보석에서 방출되는 주파수만 기록한다는 독특한 특성이 있습니다. 동점인 경우, 가장 가까운 보석 중 하나에서 방출되는 주파수를 임의로 선택합니다.

그림 G.1: 예제 입력 1에 대한 예시. 지하의 보석 아이콘은 이미 발견된 보석을 나타내며, 지표면의 점들은 오실로스코프 측정값을 나타냅니다.

당신은 방금 지표면의 다양한 고유 위치 $(x_j, 0)$에서 $N$번 오실로스코프를 사용했습니다. 당신은 이 위치들과 해당 위치에서 오실로스코프가 감지한 주파수 $f_j$를 기록했습니다. 흥미롭게도, 모든 보석의 주파수가 당신의 기록에 정확히 한 번씩 나타난다는 것을 알게 되었습니다.

다른 암석 채집가들이 아직 발견하지 못한 보석 중에서 가장 가치 있는 것을 찾고 싶습니다. 물론, 보석이 깊을수록 더 가치가 있습니다!

보석의 그럴듯한 배치(plausible configuration)란, 각 미발견 보석을 2차원 유클리드 평면 상에 배치하여 다음 조건을 만족하는 상태를 의미합니다.

• 모든 보석은 지하($y < 0$)에 있습니다.
• 주파수 $f_j$인 오실로스코프 측정값의 위치 $(x_j, 0)$에 대하여, 주파수 $f_j$를 가진 보석보다 $(x_j, 0)$에 유클리드 거리가 더 가까운 보석은 없습니다.

당신은 아직 발견되지 않은 각 보석에 대하여, 가능한 모든 보석 배치 중에서 해당 보석이 가질 수 있는 가장 깊은(가장 작은) $y$ 좌표를 계산하고자 합니다.

입력

첫 번째 줄에는 두 개의 정수 $N$ ($2 \le N \le 10^5$)과 $K$ ($1 \le K \le N - 1$)가 공백으로 구분되어 주어집니다. $N$은 묻혀 있는 보석(및 오실로스코프 측정값)의 수이고, $K$는 이미 다른 암석 채집가들에 의해 발견된 보석의 수입니다.

이어지는 $K$개의 줄에는 이미 발견된 보석의 위치와 주파수를 나타내는 세 개의 정수 $x_i$ ($|x_i| \le 10^6$), $y_i$ ($-10^6 \le y_i < 0$), $f_i$ ($1 \le f_i \le N$)가 공백으로 구분되어 주어집니다. 두 개 이상의 보석이 같은 위치에 있을 수 있습니다. $f_i$ 값은 고유함이 보장됩니다.

마지막으로 $N$개의 줄에는 오실로스코프 측정값을 나타내는 두 개의 정수 $x_j$ ($|x_j| \le 10^6$)와 $f_j$ ($1 \le f_j \le N$)가 공백으로 구분되어 주어집니다. $x_j$ 값은 고유하며 오름차순으로 정렬되어 있고, 모든 보석(발견된 보석 및 미발견 보석)은 정확히 하나의 오실로스코프 측정값을 가진다는 것이 보장됩니다. 또한 적어도 하나 이상의 그럴듯한 보석 배치가 존재함이 보장됩니다.

출력

$N - K$개의 미발견 보석 각각에 대하여, 보석의 주파수 $f_\ell$과 가능한 모든 보석 배치 중에서 해당 보석이 가질 수 있는 가장 깊은(가장 작은) $y$ 좌표 $y_\ell$을 한 줄에 출력하십시오. 이 가장 깊은 $y$ 좌표는 모든 미발견 보석에 대해 존재하며 음수이고 유한함이 증명될 수 있습니다.

이 줄들은 어떤 순서로 출력해도 상관없습니다. 미발견 보석에 대해 할당한 깊이 값이 정답과 상대 오차 또는 절대 오차 $10^{-5}$ 이내라면 정답으로 인정됩니다.

예제

예제 입력 1

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

예제 출력 1

2 -7.615773
3 -3.162278
5 -5.830952

예제 입력 2

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

예제 출력 2

3 -3.605551