Lauren đang cố gắng chơi những nốt nhạc hay nhất có thể bằng một cây đàn hạc. Cây đàn hạc là một đường tròn có bán kính \(R\) xăng-ti-mét. Để chơi một nốt nhạc, một sợi dây phải được gắn vào đàn sao cho nối hai điểm gắn khác nhau trên chu vi đường tròn. Sau đó, Lauren gảy sợi dây này để chơi một nốt nhạc.

Trên chu vi cây đàn hạc có \(N\) điểm gắn dây. Điểm gắn thứ \(i\) nằm tại vị trí cách điểm ngoài cùng bên phải của chu vi \(D_i\) nanođộ theo chiều kim đồng hồ (một nanođộ bằng \(10^{-9}\) độ).

Không phải mọi điểm gắn đều dùng cùng một công nghệ để cố định dây. Điểm thứ \(i\) cần \(L_i\) xăng-ti-mét dây cho phần gắn. Một sợi dây cố định giữa hai điểm khác nhau \(i\) và \(j\) phải dài chính xác \(L_i+L_j+\operatorname{distance}(i,j)\) xăng-ti-mét. Ở đây, \(\operatorname{distance}(i,j)\) là độ dài dây cung hình học nối hai điểm, tức khoảng cách Euclid giữa chúng.

Lauren cho rằng dây càng dài thì nốt nhạc càng hay. Hỏi \(K\) sợi dây dài nhất có thể dùng với cây đàn hạc của Lauren là những sợi nào?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Tiếp theo là \(T\) bộ test. Dòng đầu mỗi bộ test chứa ba số nguyên \(N\), \(R\), \(K\): số điểm gắn, bán kính đàn tính bằng xăng-ti-mét và số độ dài dây Lauren muốn biết.

\(N\) dòng tiếp theo mô tả các điểm gắn. Dòng thứ \(i\) chứa hai số nguyên \(D_i\), \(L_i\), lần lượt là vị trí (số nanođộ theo chiều kim đồng hồ kể từ điểm ngoài cùng bên phải) và lượng dây tính bằng xăng-ti-mét cần tại điểm thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in Case #x: y1 y2 ... yK, trong đó x là số thứ tự bộ test (bắt đầu từ \(1\)), còn yn là giá trị thứ \(n\) trong danh sách độ dài của tất cả \(N\times(N-1)/2\) sợi dây có thể dùng, sắp xếp theo thứ tự không tăng.

Mỗi yn được xem là đúng nếu sai số tuyệt đối hoặc tương đối so với đáp án đúng không quá \(10^{-9}\).

Ràng buộc

• \(1\le T\le100\).
• \(N=150000\) trong nhiều nhất \(10\) bộ test.
• \(5\le N\le10^4\) trong mọi bộ test có \(N\ne150000\).
• \(1\le R\le10^9\).
• \(0\le D_1\).
• \(D_i<D_{i+1}\) với mọi \(i\).
• \(D_N<360\times10^9\).

Phân nhóm

Test Set 1 (Phán quyết hiển thị)

• Với mỗi \(i\), \(L_i\) được chọn độc lập và ngẫu nhiên đều từ \(1\) đến \(10^9\), kể cả hai đầu.
• \(K=1\).

Test Set 2 (Phán quyết ẩn)

• \(1\le L_i\le10^9\) với mọi \(i\).
• Không có bảo đảm nào về cách sinh từng \(L_i\).
• \(K=10\).

Đ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ụ

5 2 1
0 3
1234567890 3
3154510113 3
180000000000 3
359999999999 3
5 10 1
90000000000 8
180000000000 7
260000000000 9
260000000001 1
260000000002 1
???+ success "Output"sample
Case #1: 10.0000000000
Case #2: 36.9238939618
```

??? "Giải thích"
    Các bộ test trên thỏa mãn ràng buộc Test Set 1. Một bộ test mẫu không thỏa mãn các ràng buộc đó nằm ở cuối phần này.

    Lưu ý: các giá trị $L_i$ trong những mẫu Test Set 1 được chọn cho dễ hiểu chứ không được sinh ngẫu nhiên. Lời giải vẫn được chạy với các mẫu này và phải cho kết quả đúng.

    Trong mẫu số 1, mọi điểm gắn có cùng giá trị, nên ta chọn cặp nối bởi dây cung dài nhất: đường kính nằm ngang dài $4$ xăng-ti-mét. Tổng độ dài cần là $4+3+3=10$ xăng-ti-mét.

    Trong mẫu số 2, điểm thứ tư và thứ năm cực kỳ gần điểm thứ ba nhưng có giá trị $L$ nhỏ hơn nhiều. Ta có thể loại chúng và tập trung vào các cách nối giữa ba điểm đầu:


    - Điểm thứ nhất và thứ hai: $10\sqrt2+8+7\approx29.142136$.
    - Điểm thứ nhất và thứ ba: $\approx19.923894+8+9\approx36.923894$.
    - Điểm thứ hai và thứ ba: $\approx12.855726+7+9\approx28.855726$.

    Nối điểm thứ nhất và thứ ba cho tổng độ dài lớn nhất.

    Bộ test bổ sung sau không thể xuất hiện trong Test Set 1 nhưng có thể xuất hiện trong Test Set 2.

    ```sample
    1
    6 1 10
    0 10
    15000000000 1
    30000000000 1
    45000000000 1
    60000000000 1
    75000000000 1
    ```

    Kết quả đúng là:

    ```sample
    Case #1: 12.2175228580 12.0000000000 11.7653668647 11.5176380902 11.2610523844 3.0000000000 2.7653668647 2.7653668647 2.5176380902 2.5176380902
    ```

    Có ba cặp điểm cùng tạo ra sợi dây dài thứ chín. Ngoài ra, các đoạn nối những cặp khác nhau có thể cắt nhau, vì Lauren mỗi lần chỉ chơi một nốt.

Nguồn

Google Code Jam 2020, Chung kết thế giới trực tuyến, bài Musical Cords.

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