Giải bài trực tuyến

Công ty XYZ là một công ty chuyên vận chuyển đồ chơi đến tận nhà cho các bé. Năm nay, nhân dịp Noel, công ty XYZ tổ chức một sự kiện phát quà trên diện rộng, huy động V xe tải để phát quà đến nhà của N-1 bé.

Chúng ta sẽ mô phỏng địa điểm của công ty XYZ và nhà của N-1 bé bằng N điểm trên mặng phẳng tọa độ 2 chiều:

• Công ty XYZ có tọa độ (x₀, y₀).
• Nhà của bé thứ i có tọa độ (x_i, y_i) với i = 1..N-1.

Mỗi xe của công ty sẽ xuất phát từ công ty XYZ, đi qua nhà một số bé và quay trở về công ty XYZ.

Yêu cầu:

• Nhà của mỗi bé phải được đi qua đúng một lần (nói cách khác, không có 2 xe tải nào cùng đi qua nhà của một bé).
• Món quà cần chuyển đến nhà của bé thứ i có khối lượng d(i). Xe tải chỉ được chở không quá C khối lượng hàng hóa.
• Mỗi xe tải hoặc là không di chuyển, hoặc là xuất phát từ công ty XYZ, đi qua nhà của một số bé và quay trở về công ty XYZ. Sau đấy xe tải phải dừng lại, không được di chuyển tiếp nữa. (Nói cách khác, đường đi của xe tải sẽ tạo 1 đường gấp khúc khép kín, đi qua công ty XYZ đúng 2 lần: lúc xuất phát và lúc kết thúc. Chú ý rằng nếu xe tải không di chuyển có thể hiểu là đường gấp khúc độ dài bằng 0).
• Chú ý rằng vì xe chỉ được di chuyển không quá 1 vòng, nên tất cả các món quà chở đến nhà các bé phải được chất lên xe tại thời điểm xe xuất phát.

Là người đứng đầu công ty XYZ, bạn cần phải tìm hành trình của các xe tải sao cho tổng độ dài tất cả V xe tải phải di chuyển là nhỏ nhất, và không có xe tải nào phải vận chuyển quá C khối lượng hàng hóa. Biết rằng các xe di chuyển từ điểm (x₁, y₁) đến điểm (x₂, y₂) theo con đường ngắn nhất với độ dài được tính theo khoảng cách Euclid giữa 2 điểm.

Input

Dòng 1: 3 số nguyên dương N, V, C

N dòng tiếp theo, dòng thứ i (i đánh số từ 0 đến N-1) chứa số nguyên di và 2 số thực x_i, y_i:

• Với i = 0, d_i = 0, (x_i, y_i) là tọa độ công ty XYZ
• Với i > 0, d_i là khối lượng món quà cần chuyển đến nhà bé thứ i, (x_i, y_i) là tọa độ nhà bé thứ i.

Output

Gồm đúng V dòng, dòng thứ i gồm các số nguyên - thể hiện trình tự nhà các bé mà xe tải đi qua. Điểm đầu tiên và điểm cuối cùng của hành trình phải bằng 0. Các điểm còn lại phải lớn hơn 0.

Giới hạn:

• N ≤ 500
• V ≤ 50
• d_i, C ≤ 40,000
• |x_i|, |y_i| ≤ 10,000

Cách tính điểm:

• Nếu một xe của bạn chở quá C kg hàng hóa, bạn nhận được 0 điểm.
• Nếu có một điểm không được chở hàng đến, bạn nhận được 0 điểm.
• Trong trường hợp còn lại
  • Đặt X = tổng độ dài các xe bạn di chuyển
  • Đặt Y = độ dài mà ban tổ chức đưa ra.
  • Điểm của bạn nhận được bằng min(Y/X, 3).
• Vì bài này thuộc dạng challenge, nên điểm chung cuộc của bạn trong kỳ thi VM14 sẽ được tính theo công thức:
  • Giả sử điểm của bạn đứng thứ i (nghĩa là có i-1 người điểm cao hơn bạn).
  • Điểm của bạn nhận được là
    
    với log là log cơ số e.
• Bài này gồm có đúng 64 test. Trong quá trình thi, bạn được chấm với 16 test.

Example

Input:
5 4 10

0 0.0 0.0

3 0.0 10.0

3 -10.0 10.0

3 0.0 -10.0

3 10.0 -10.0

Output:
0 1 2 3 0

0 4 0

0 0

0 0

Với output này, tổng độ dài các xe của bạn di chuyển là 80.6 (X = 80.6). Giả sử độ dài mà ban tổ chức đưa ra cũng là 80.6 (Y = 80.6), thì điểm bạn nhận được cho test này là 1