406598: GYM102452 F Falling Objects

F. Falling Objectstime limit per test5.5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

On Sky Island, architects always use IslandClouds as materials to build all kinds of marvellous structures. Today, a sculpture competition is being held on Sky Island. Each architect needs to build some fancy sculptures with three kinds of meta IslandClouds. These three kinds of IslandClouds are in the shapes of spheres, cubes and regular tetrahedrons, and they come in different sizes. Of course, because they are clouds, once an IslandCloud touches another IslandCloud, they are glued together.

Asira, a famous architect on Sky Island, is now working hard on his great works. He is going to perform a series of operations to build his sculptures. In each operation, he picks an IslandCloud, rotates it and then moves it to someplace that is high enough, release it and let it fall down freely until it is glued to another IslandCloud or the ground (the ground of Sky Island is also made of IslandClouds). Asira will only release an IslandCloud after the previous one is glued.

Formally, you may assume the three types of IslandClouds are initially in the postures shown in the figures below, with their geometric centres at the world $$$(xyz)$$$ coordinates $$$(0, 0, 0)$$$ and the three object coordinate axes $$$(XYZ)$$$ each coincides with the corresponding world coordinate axes $$$(xyz)$$$. Here the world $$$(xyz)$$$ coordinates is assumed to remain motionless while the object $$$(XYZ)$$$ coordinates is solidary with the moving body which changes its orientation after each rotation.

An IslandCloud in the shape of a cube. An IslandCloud in the shape of a sphere. An IslandCloud in the shape of a regular tetrahedron.

To make a beautiful sculpture, Asira rotates the IslandCloud with the following process before letting it fall (it is called $$$zXZ-(\alpha, \beta, \gamma)$$$ proper Euler Angles):

1. The object $$$(XYZ)$$$ coordinates rotates about the $$$z$$$ axis by $$$\alpha$$$ together with the object. The $$$X$$$ axis is now at angle $$$\alpha$$$ with respect to the $$$x$$$ axis (according to the right-hand rule).
2. The object $$$(XYZ)$$$ coordinates rotates about the $$$X$$$ axis by $$$\beta$$$ together with the object.
3. The object $$$(XYZ)$$$ coordinates rotates about the $$$Z$$$ axis by $$$\gamma$$$ together with the object.

Note that collision with other IslandClouds can be ignored until the IslandCloud is released.

After that, the IslandCloud is moved so that its centre is at $$$(x, y, +\infty)$$$ in world coordinates and is then released. The $$$z$$$ coordinate starts to decrease as the IslandCloud falls until it touches another IslandCloud (any point on the falling IslandClould coincides with any point on another IslandClould). Once that happens, the IslandCloud immediately stops moving and becomes glued, which means it can never move again. Don't forget that the ground, which is the $$$xOy$$$ plane, is also made of IslandClouds.

Now, Asira wants to know the $$$z$$$ coordinate of the highest point of each IslandCloud once it is glued.

Input

The input contains multiple cases. The first line of the input contains a single integer $$$T$$$ ($$$1 \le T \le 1\,000$$$), the number of cases.

For each case, the first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 1\,000$$$), the number of IslandClouds used by Asira. In the following $$$n$$$ lines, the $$$i$$$-th line $$$(1 \le i \le n)$$$ contains seven integers $$$type_i$$$, $$$\alpha_i$$$, $$$\beta_i$$$, $$$\gamma_i$$$, $$$x_i$$$, $$$y_i$$$ and $$$r_i$$$ ($$$0 \le type_i \le 2$$$, $$$0 \le \alpha_i, \beta_i, \gamma_i < 360$$$, $$$-10^4 \le x_i, y_i \le 10^4$$$, $$$1 \le r_i \le 10^4$$$), denoting the type of the $$$i$$$-th IslandCloud used by Asira in chronological order (0 for cube, 1 for sphere and 2 for regular tetrahedrons), its the proper Euler Angles of the rotation, its $$$x$$$, $$$y$$$ coordinates before being released and its size (radius for spheres, or side length for cubes and regular tetrahedrons), repectively. Note that the units of $$$\alpha_i, \beta_i, \gamma_i$$$ are degrees.

It is guaranteed that the sum of $$$n$$$ over all cases does not exceed $$$1\,000$$$.

Output

For each test case, print $$$n$$$ lines, where the $$$i$$$-th $$$(1 \le i \le n)$$$ line should contain a single real number, the $$$z$$$ coordinate of the highest point of the $$$i$$$-th IslandCloud. Your answer will be considered correct if and only if the absolute or relative error does not exceed $$$10^{-4}$$$.

ExampleInput

3
2
0 45 90 270 0 0 2
1 11 45 14 0 0 1
2
0 45 90 0 0 0 2
1 112 345 67 8 9 99
1
2 191 98 10 25 25 2

Output

2.000000000000001
4.000000000000001
2.000000000000001
199.384661561446364
1.950447343314250