DIST - Distance

You are given the coordinates of N cities (xi,yi). Each city also has a popularity value, pi. You have to place a new city (x,y) such that the sum of distances of this new point from all the other given points is minimized.
Distance of the new point from a given city i is given by :
d = |xi - x| ^ pi + | yi - y | ^ pi

Input

There are multiple test cases.
First line contains the number of testcases.
Each testcases starts with the number N, the number of points.
This is followed by the descriptions of each in the format
xi yi pi
The input consists of only integers

Output

For each testcase, output the minimum distance obtained, with exactly 3 digits after the decimal point.

Example

Input:
1
3
1 2 0
4 5 1
2 4 2
Output: 4.500

Constraints

No. of testcases <= 10
N <= 10^5
|xi,yi| <= 1000
0 <= pi <= 3


Added by:Kunal Jain
Date:2011-02-07
Time limit:1.303s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CodeCraft 11

hide comments
2011-02-11 14:19:30 abhijith reddy d
Tip: Reading input itself takes 3+ secs. (scanf/printf)
2011-02-09 16:38:56 numerix
... not for all languages
2011-02-09 07:41:20 mike_nzk
time limit so large...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.