Find the Circle

Given three circles (center of them are not co-linear), your job is to find a circle that is tangent with all these three circles. However, the circle might be not unique, as they can be either externally or internally tangent to each other. To make it clearer, you have to give the answer in some specific model. For example, you might be asked to give a circle which should be internally tangent with circle 1 and circle 2, while externally tangent with circle 3.

The first line of input contains an integer n, which is the number of test cases. Each case have three lines, each have four integers x, y, r, m. (0 <= x, y <= 10000 and 0 <= r <= 500), where x, y is position of one circle, and r is the radius. m represents the model of circle you should give. m = 0 means your circle should internally tangent with this circle, and m = 1 for externally case.

Output x, y, r in one line (accurate to 10^ (-4)). The circle required may not exist. If it is a point(r = 0), just output a point with x and y, do not output r (which is zero). If you just even cannot find a point, too, just output "NO SOLUTION!"

2
1 3 2 0
0 1 5 0
1 0 1 0
3 5 20 1
2 1 1 1
4 4 1 1

-0.4904 2.2264 3.6792
NO SOLUTION!

2011 Multi-University Training Contest 6 - Host by JLU