치즈 자르기

치즈 가공 회사가 공 모양 치즈를 무게가 똑같은 조각으로 자르는 기계를 만들었다. 다음 목표는 구멍이 뚫린 스위스 치즈다.

에멘탈 같은 치즈에는 크기가 제각각인 구멍이 있다. 구멍이 많이 든 조각은 치즈가 적게 들어 있으니 그만큼 가볍다. 그래서 문제는 이것이다. 구멍이 있는 치즈를 무게가 같은 조각으로 자르려면 어떻게 해야 하는가.

초음파 검사로 구멍의 위치를 마이크로미터 단위까지 알아낼 수 있다. 이 문제에서 구멍은 모두 완전한 구라고 가정한다. 치즈의 밀도는 어디서나 같으므로 조각의 무게는 치즈 부분의 부피에 비례한다.

자르기 전 덩어리는 한 변이 $100$ 밀리미터인 정육면체다. 이 덩어리를 무게가 같은 $s$개의 조각으로 자른다. 각 조각은 너비 $100$ 밀리미터, 높이 $100$ 밀리미터이고, 구할 것은 조각마다의 두께다.

첫째 줄에 구멍의 개수 $n$과 조각의 수 $s$가 주어진다. $0 \le n \le 10\,000$이고 $1 \le s \le 100$이다.

다음 $n$개 줄에는 구멍 하나를 나타내는 양의 정수 네 개 $r$, $x$, $y$, $z$가 주어진다. $r$은 반지름, $(x, y, z)$는 중심의 좌표이고 단위는 모두 마이크로미터다.

치즈 덩어리는 $0 \le x, y, z \le 100\,000$을 만족하는 점 가운데 어떤 구멍에도 속하지 않는 점으로 이루어진다. 자르는 면은 $z$축에 수직이다.

구멍끼리는 겹치지 않지만 서로 접할 수 있다. 모든 구멍은 치즈 안에 완전히 들어 있고, 치즈의 경계면에 접할 수 있다.

$z = 0$ 쪽 끝에서 시작해 $s$개 조각의 두께를 밀리미터 단위로 한 줄에 하나씩 출력한다.

각 두께는 소수점 아래 아홉째 자리까지 반올림해, 소수점 아래 자릿수가 정확히 아홉 개가 되도록 출력한다.