Aerobics Mat Placement

An aerobics class is about to start. The trainer tells the students to spread out on the training mat so that everyone can swing her arms without hitting anybody. The students keep shuffling around without settling down, so the trainer asks you to compute the positions instead.

The mat is a rectangle of width $W$ and length $L$. Student $i$ needs a disc of radius $r_i$, the reach of her arms, all to herself. Two discs may touch but may not overlap. Each student stands on the mat, so her center satisfies $0 \le x \le W$ and $0 \le y \le L$. Arms may reach past the edge of the mat.

The mat is roomy: its area is at least five times the total area of the discs. A valid arrangement always exists, and the output section fixes the single arrangement you must print.

The first line contains the number of test cases $T$. Each test case is two lines. The first line contains three integers $N$, $W$ and $L$: the number of students, the width of the mat and the length of the mat. The second line contains $N$ integers $r_1, r_2, \dots, r_N$, the reach of the arms of each student.

Limits

• $1 \le T \le 50$
• $1 \le N \le 10$
• $1 \le W, L \le 10^9$
• $1 \le r_i \le 10^5$
• $5\pi(r_1^2 + r_2^2 + \dots + r_N^2) \le W \cdot L$

For each test case print one line "Case #n: " followed by $2N$ integers $x_1\ y_1\ x_2\ y_2\ \dots\ x_N\ y_N$ separated by single spaces, where $(x_i, y_i)$ is the position of student $i$ and $n$ is the case number starting from 1. Print exactly the arrangement that the following construction produces.

Let $R$ be the largest reach in the test case. Students are placed in rows, in input order. A row takes students until one no longer fits, and that student opens the next row.

If $W \ge L$, the rows are parallel to the $x$ axis. Every student in row $j$, counted from $j = 0$, has $y = 2Rj$. The first student of a row has $x = 0$. For any other student, let $p$ be the $x$ coordinate of the student placed just before her in the same row, $r_p$ that student's reach and $r_c$ her own reach. She takes $x = p + r_p + r_c$ when this value is at most $W$; when it is greater than $W$, she opens the next row at $x = 0$ instead.

If $W < L$, apply the same construction with the two axes exchanged: every student in row $j$ has $x = 2Rj$, the coordinate chosen inside a row is the $y$ coordinate, and the value compared against is $L$.

Every coordinate this construction produces is an integer, and the limits guarantee that all students stay on the mat.