Old Mirko has a son: Mirko junior. A while ago, Mirko senior bought Mirko junior a lot of plastic balls of various sizes. The junior has learned a lot by playing with them.
Now that the junior has grown older, Mirko senior would like to give his son harder challenges. One day after another play session, Mirko senior asked him to put away all balls into a wooden box for easier storage. Unfortunately, Mirko junior is struggling to put everything into the box. Can you help him?
You are given an empty wooden box of dimensions w × h × d. You are also given a number of plastic balls. Your task is to place all balls into the box. All balls must be completely inside the box. No two balls may intersect. Any such placement will be accepted. In particular, when constructing the placement of balls in the box you may ignore gravity and leave some of the balls floating in the air without support.
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of a number of lines.
The first line contains floating point numbers w, h, d, (1 ≤ w, h, d ≤ 250) specifying the dimensions of the wooden box. The box has one corner at x, y, z coordinate (0, 0, 0) and the opposite one at (w, h, d).
The second line contains an integer n, specifying the number of different types of balls. Each ball type is described by a line containing two numbers c and r. The integer c, (1 ≤ c ≤ 150), specifies the number of copies of the ball type you own and the floating point number r, (0.001 ≤ r ≤ 15), specifies the radius of the balls. There are at most 150 balls in total and all floating point numbers have at most 8 digits after the decimal point.
In the easy subproblem B1, 1 ≤ n ≤ 2. In the hard subproblem B2, 1 ≤ n ≤ 5.
For each test case, print multiple lines. Print an empty line after each case.
The output for each test case should contain as many lines as there are balls in the box, each line describing one of the balls. The description of each ball has the form “i x y z”, where i is the type of the ball and (x, y, z) are the coordinates of its center. Ball types are numbered 1 through n in the order in which they appeared in the input.
Balls can be printed in any order, but make sure to use exactly the entire set of the balls you own. All balls must fit inside the box. A solution is guaranteed to exist.
Your answer should have an absolute error of at most 10−6, in particular:
Input:
1
8 8 8
2
1 4
2 0.9Output:
1 4 4 4
2 1 7 1
2 1 7 7