Aerobics (Large)

The aerobics class begins. The trainer asks the students to stand on the mat so that everybody can swing her arms freely without hitting anybody else. The students keep milling around, so the trainer asked for a program that assigns the positions instead.

The mat is a rectangle of width $W$ and length $L$. Student $i$ needs a circle of radius $r_i$ around the point where she stands, where $r_i$ is the reach of her arms. Two circles may touch but may not overlap, so the distance between the centers of student $i$ and student $j$ has to be at least $r_i + r_j$. Every center has to lie on the mat, that is $0 \le x_i \le W$ and $0 \le y_i \le L$. The arms may reach outside the mat.

The mat is roomy. Its area is at least five times the total area of the circles, so $5\pi(r_1^2 + \cdots + r_N^2) \le W \cdot L$ holds and a valid placement always exists.

Many placements are valid, so this problem accepts only the one placement produced by the rule given in the output section.

The first line contains the number of test cases $T$. Each test case consists of two lines. The first line contains the number of students $N$, the width $W$ of the mat, and the length $L$ of the mat, separated by spaces. The second line contains $N$ integers $r_1, \ldots, r_N$, where $r_i$ is the reach of the arms of student $i$.

The constraints are the following.

• $1 \le T \le 50$
• $1 \le N \le 1000$
• $1 \le W, L \le 10^9$
• $1 \le r_i \le 10^5$
• $5\pi(r_1^2 + \cdots + r_N^2) \le W \cdot L$
• The sum of $N$ over all test cases is at most 6000.

For each test case print one line that starts with Case #n: and continues with $2N$ integers separated by single spaces. Here $n$ is the number of the test case, counting from 1, and the integers are $x_1$, $y_1$, $x_2$, $y_2$ and so on in the input order, where $(x_i, y_i)$ is the point at which student $i$ stands.

The placement is fixed by the following rule.

First sort the students by reach, largest first. Students with the same reach keep their input order. Call the result the placement order.

If $W \ge L$, the students are grouped into vertical lines. The students of one line share the same $x$ and get increasing $y$. In that case the length of a line is bounded by $S = L$, the coordinate $f$ that moves inside a line is $y$, and the coordinate $g$ that moves from line to line is $x$. If $W < L$, the two axes are exchanged and the lines are horizontal. The students of one line share the same $y$ and get increasing $x$, with $S = W$, $f = x$ and $g = y$.

Take the students one at a time in placement order and add each to the current line.

• The first line has $g = 0$.
• The first student of a line stands at $f = 0$.
• Any other student $i$ is placed relative to the student $p$ placed just before her. If $p$ has reach $r_p$ at coordinate $f_p$ and $f_p + r_p + r_i \le S$, then student $i$ joins the same line at $f = f_p + r_p + r_i$.
• Otherwise student $i$ opens a new line. If $R$ is the reach of the first student of the line being closed, the new line has $g$ equal to the $g$ of the closed line plus $R + r_i$, and student $i$ stands at $f = 0$ of that new line.

Every coordinate this rule produces is an integer, and under the constraints of the problem every coordinate stays on the mat.