Submit | All submissions | Best solutions | Back to list |

## 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 <= *x*_{1}, *y*_{1}, *x*_{2}, *y*_{2} <= 1000, where *x _{i}*,

*y*are the coordinates of the endpoints of the line segment.

_{i}### 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 10Output: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 |