SANTA - Santa Claus and the Presents

Every year Santa Claus faces a more and more difficult task. The number of children in the world is increasing rapidly, while Santa's old patched up sack can only accommodate a few presents at a time. And every child wants their own very special present... This means that, ever so often, once his sack is partially or completely empty, Santa has to fly back to his base in Lapland to replenish his supplies. So irksome has this become that Santa has decided to resort to modern operational research to aid him in his sack-packing and route planning. Please write a program which will guide Santa through his daily chores.

Input

The input starts with a line containing a single integer t<=100, the number of test cases. t test cases follow.

The first line of every test case consists of four integers n x y S, denoting the number of good children who will receive a present from Santa, the x and y coordinates of Santa's home base, and the amount of space in the sack, respectively (1<=n<=10000, -10000<=x,y<=10000, 1<=S<=100000). n lines follow, each consisting of three integers xi yi si - the x and y coordinates of the i-th child's home, and the amount of space taken up by this child's present when in Santa's sack, respectively (-10000<=xi,yi<=10000, 1<=si<=S).

Output

For each test case output a sequence of space separated integers, corresponding to successive actions that should be taken by Santa:

  • -i (1<=i<=n) signifies that Santa should travel to his base and pack the present for the i-th child into his sack (he needs to have sufficient room in his sack to do this).
  • i (1<=i<=n) signifies that Santa should travel to the i-th child's home and leave a present for him/her.
  • 0 signifies that Santa should travel back to his base and end his Christmas activity (and that you want to proceed to the next test case).

Assume that Santa starts in his base and always travels between points by the shortest possible route (along straight lines). All distances are measured using the Euclidean metric.

Score

The score awarded to your program is the total of all scores obtained for its individual test cases. The score for a test case is calculated as I/P, where P stands for the distance covered by Santa in your solution, while I is a test case specific constant (I= n*d+D*(s1+...+sn)/S; d is the mean distance between two homes, while D is the mean distance between Santa's base and a child's home for the given test case).

No points are awarded for incompletely solved test cases (when not all the children receive presents). Any other violation of transport rules results in Wrong Answer.

Example

Input:
1
3 0 0 3
1 0 1
1 0 2
1 0 3

Output:
-1 -2 1 2 -3 3 0

Score:
2/(1+1+1+1)= 0.5

Added by:Krzysztof Kluczek
Date:2004-12-09
Time limit:17s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Resource:DASM Programming League 2004, problemset 4

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