Cutting Cheese

Time limit3sMemory limit256 MB

Summary

Cut a 100 mm cube with spherical holes into s slices of equal cheese volume perpendicular to the z axis and print each thickness.

Level: Medium6 of 10
Topics: Binary search, Geometry, Math
Solved: No attempts yet

Problem

A cheese processing company built a machine that cuts a spherical cheese into slices of exactly equal weight. The next target is Swiss cheese, which has holes in it.

A cheese such as Emmentaler contains holes of different sizes. A slice with many holes holds less cheese, so it weighs less. The problem is how to cut a cheese with holes into slices of equal weight.

Sonar scanning locates the holes down to micrometer precision. In this problem every hole is a perfect sphere. The cheese has uniform density, so the weight of a slice is proportional to the volume of cheese in it.

An uncut block is a cube $100$ millimeters on each side. Cut it into $s$ slices of equal weight. Every slice is $100$ millimeters wide and $100$ millimeters high, and you have to determine the thickness of each slice.

Input

The first line contains the number of holes $n$ and the number of slices $s$ , where $0 \le n \le 10\,000$ and $1 \le s \le 100$ .

Each of the next $n$ lines contains four positive integers $r$ , $x$ , $y$ , and $z$ describing one hole. Here $r$ is the radius and $(x, y, z)$ is the center, all measured in micrometers.

The block occupies the points with $0 \le x, y, z \le 100\,000$ that belong to no hole. The cuts are perpendicular to the $z$ axis.

Holes do not overlap, but they may touch each other. Every hole lies entirely inside the cheese and may touch its boundary.

Output

Print the thickness of each of the $s$ slices in millimeters, one per line, starting from the $z = 0$ end of the block.

Round each thickness to nine places after the decimal point and print exactly nine digits after the decimal point.

Examples4

Example 1

Input

0 4

Expected output

25.000000000
25.000000000
25.000000000
25.000000000

Example 2

Input

2 5
10000 10000 20000 20000
40000 40000 50000 60000

Expected output

14.611103142
16.269801734
24.092457788
27.002992272
18.023645064

Example 3
Input
```
0 1
```
Expected output
```
100.000000000
```

Example 4

Input

0 3

Expected output

33.333333333
33.333333333
33.333333333