## NECKLACE - Necklace

There are **N** points marked on a surface, pair (**x _{i}**,

**y**) is coordinates of a point number

_{i}**i**. Let's call a

*necklace*a set of

**N**figures which fulfills the following rules.

- The figure
**#i**consists of all such points (**x**,**y**) that (**x**-**x**)_{i}+ (^{2}**y**-**y**)_{i}≤^{2}**r**_{i}, where^{2}**r**≥_{i}*0*. - Figures
**#i**and**#(i+1)**intersect (*1*≤**i**<**N**). - Figures
*#1*and**#N**intersect. - All the rest pairs of figures do not intersect.

Write a program which takes points and constructs a necklace.

### Input

First line of input contains an integer **t** (*1* ≤ **t** ≤ *45*), equals to the number of testcases. Then descriptions of **t**
testcases follow.

The first line of the description contains one integer number **N** (*2* ≤ **N** ≤ *100*).
Each of the next **N** lines contains two real numbers **x _{i}**,

**y**(

_{i}*-1000*≤

**x**,

_{i}**y**≤

_{i}*1000*), separated by one space. It is guaranteed that at least one necklace exists for each testcase.

### Output

For each testcase your program should output exactly **N** lines. A line **#i** should contain real number **r _{i}** (

*0*≤

**r**<

_{i}*10000*). To avoid potential accuracy problems, a checking program uses the following rules.

- Figures
**#i**and**#j**definitely do not intersect if**r**+_{i}**r**≤_{j}**d**-_{ij}*10*.^{-5} - Figures
**#i**and**#j**definitely intersect if**d**+_{ij}*10*≤^{-5}**r**+_{i}**r**._{j} - The case when
**d**-_{ij}*10*<^{-5}**r**+_{i}**r**<_{j}**d**+_{ij}*10*is decided in favour of a contestant.^{-5} **d**equals_{ij}*sqrt*((**x**-_{i}**x**)_{j}+ (^{2}**y**-_{i}**y**)_{j}) in the rules above.^{2}

### Example

Input:1 4 0 0 10 0 10 10 0 10Output:7 7 7 7

hide comments

yangshen:
2012-05-25 08:53:24
I have solved this problem by simplex algorithm,but it is too slow and got TLE on poj,how to solve it faster? |

Added by: | Ivan Metelsky |

Date: | 2005-08-25 |

Time limit: | 1.632s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: NODEJS PERL6 VB.NET |

Resource: | NEERC Western Subregion QF 2004 |