Lớp học thể dục nhịp điệu bắt đầu. Huấn luyện viên nói: "Các em hãy đứng trên thảm tập sao cho mỗi người đều có đủ không gian để vung tay thoải mái mà không va trúng bất kỳ ai khác." Mọi người bắt đầu di chuyển trên thảm, cố gắng tìm vị trí thích hợp. Nhiều phút trôi qua, cuối cùng huấn luyện viên quá khó chịu nên đã nhờ bạn viết một chương trình để sắp xếp vị trí cho tất cả mọi người, hy vọng việc này sẽ nhanh hơn là để họ tự loay hoay!

Bạn được cho kích thước (chiều rộng và chiều dài) của tấm thảm nơi lớp học diễn ra. Đối với mỗi học sinh, có một khu vực hình tròn mà cô ấy cần cho riêng mình, với bán kính bằng tầm với của cánh tay. Các hình tròn này không được giao nhau, mặc dù chúng có thể tiếp xúc; và tâm của mỗi hình tròn (nơi học sinh đứng) phải nằm trên thảm. Lưu ý rằng cánh tay có thể vươn ra ngoài phạm vi tấm thảm. Bạn biết rằng có rất nhiều không gian trên thảm — diện tích của thảm ít nhất gấp năm lần tổng diện tích các hình tròn cần thiết cho tất cả mọi người trong lớp. Sẽ luôn có cách để tất cả mọi người đứng vào vị trí như yêu cầu.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo. Mỗi bộ thử nghiệm gồm hai dòng. Dòng đầu tiên chứa ba số nguyên: \(N\), \(W\) và \(L\), lần lượt biểu thị số lượng học sinh, chiều rộng của thảm và chiều dài của thảm. Dòng thứ hai chứa \(N\) số nguyên \(r_i\), biểu thị tầm với cánh tay của học sinh thứ \(i\).

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #n: y", trong đó n là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là một chuỗi chứa \(2N\) số, mỗi số có thể là số nguyên hoặc số thực: \(x_1, y_1, x_2, y_2\), v.v., trong đó cặp (\(x_i, y_i\)) là vị trí học sinh thứ \(i\) nên đứng (với \(0 \le x_i \le W\) và \(0 \le y_i \le L\)).

Vì có thể có nhiều cách để sắp xếp các học sinh trên thảm, bạn có thể xuất bất kỳ cách sắp xếp chính xác nào; nhưng hãy nhớ rằng bạn không được gửi tệp đầu ra có kích thước quá 200kB.

Ràng buộc

• \(1 \le T \le 50\).
• \(1 \le W, L \le 10^9\).
• \(1 \le r_i \le 10^5\).
• Diện tích thảm ít nhất gấp 5 lần tổng diện tích các hình tròn: \(5 \cdot \pi \cdot (r_1^2 + \dots + r_N^2) \le W \cdot L\).

Phân nhóm

• Tập thử nghiệm 1 (Visible): \(1 \le N \le 10\).
• Tập thử nghiệm 2 (Hidden): \(1 \le N \le 10^3\). Tổng số hình tròn trong tất cả các bộ thử nghiệm \(\le 6000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
2 6 6
1 1
3 320 2
4 3 2

Case #1: 0.0 0.0 6.0 6.0
Case #2: 0.0 0.0 7.0 0.0 12.0 0.0

Nguồn

Google Code Jam 2012, Vòng 2, bài Aerobics.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.