Programming League 2004/05

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 x_i y_i s_i - 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<=x_i,y_i<=10000, 1<=s_i<=S).

Output

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

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*(s₁+...+s_n)/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