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:All except: ASM32-GCC GAWK MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV ICK JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SED SQLITE SWIFT UNLAMBDA VB.NET
Resource:High School Programming League

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