Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS12INSP - Intersection Point

Given a circle and a line segment compute their point of intersection. You can assume that one of the endpoints of the line segment belongs to the interior of the circle, while the other to the exterior.

Input

First t < 1000, the number of test cases. In each of the following t lines, 7 integers: -1000 <= x, y <= 1000, where x and y are the circle center coordinates and 0 < r <= 1000 the radius of the circle; -1000 <= x1, y1, x2, y2 <= 1000, where xi, yi are the coordinates of the endpoints of the line segment.

Output

For each test case print the intersection point coordinates with two digits of precision.

Example

Input:
2
0 0 1 0 0 0 2
10 10 10 15 10 25 10

Output:
0.00 1.00
20.00 10.00 

Scoring

By solving this problem you score 10 points.


Added by:kuszi
Date:2012-10-03
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 ASM64 BASH BF C CSHARP C++ 4.3.2 CPP C99 CLPS CLOJURE LISP sbcl LISP clisp D ERL FSHARP FORTRAN GO HASK ICON JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PERL6 PHP PIKE PRLG-swi PYTHON PYTHON3 RUBY SCALA SCM guile SCM qobi ST TCL WHITESPACE
Resource:High School Programming League

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.