Contraband#6395

Contraband

1 second

64 megabytes

Medium

It has been reported that something fell out of an aircraft approaching the airport over the bay. Thinking the object may have been some sort of contraband to be picked up by a confederate, the police want to watch for a repeat whenever any of the aircraft that could have been the one that dropped the object again approaches the airport over the bay. Three observation stations with night vision equipment have been stationed around the bay (see figure below).

Station $1$ is $3.715$ kilometers east and $1.765$ kilometers north of station $0$ and station $2$ is $2.894$ kilometers east and $2.115$ kilometers south of station $0$ .

When a suspect aircraft crosses the bay, each observer follows it with the night vision equipment while in contact with the other. If one observer sees something falling from the aircraft, each records a direction to the object and a confidence level for that direction. The confidence level (CL) is a value from $0$ (more or less pointing at the aircraft) to $1$ (pointing at the splash where the object hit the water).

In general, the three sight lines will not cross at a single point but will form a triangle (See Intersection Detail above). The best estimate of the actual position is to be the point ( $x$ , $y$ ) which minimizes the sum of the squares of the distances $d_{i}$ d_i, to each line, weighted by the confidence level, $C L_{i} + 0.2$ CL_i + 0.2,

Minimize

i = 0 \sum 2 (C L_{i} + 0.2) \cdot d_{i}^{2}

\sum_{i=0}^{2} (CL_i + 0.2) \cdot d_i^2

For this problem, you will write a program which takes as input the three observer directions and the three confidence levels and outputs the point ( $x$ , $y$ ), which minimizes the above sum, where $x$ is the distance in kilometers east of station $0$ and $y$ is the distance in kilometers north (positive) or south (negative) of station $0$ .

Input

The first line contains the number of data sets $p$ ( $1 \leq p \leq 1000$ 1 \leq p \leq 1000) that follow. Each data set should be processed identically and independently.

Each data set is a single line consisting of the data set number $n$ , followed by a space, and six space separated floating point values. The floating point values are, in order $a_{0}$ a_0, $C L_{0}$ CL_0, $a_{1}$ a_1, $C L_{1}$ CL_1, $a_{2}$ a_2, $C L_{2}$ CL_2. $a_{i}$ a_i is the bearing (in degrees clockwise from north) from station $i$ ( $0 \leq a_{i} \leq 360$ 0 \leq a_i \leq 360) and $C L_{i}$ CL_i is the confidence level of observer $i$ ( $0 \leq C L_{i} \leq 1$ 0 \leq CL_i \leq 1).

Output

For each data set there is one line of output. It contains the data set number, N, followed by a single space which is then followed by two space separated values $x$ and $y$ . $x$ is the distance east of station $0$ in kilometers, and $y$ is the distance north (positive) or south (negative) of station $0$ . The distances should be displayed to $3$ decimal places.

Examples

Example 1