Bộ lập lịch Round-Robin

Bối cảnh và bài toán

Một CPU xử lý n tiến trình theo Round-Robin. Ban đầu các tiến trình 1..n vào hàng theo thứ tự. Mỗi lần lấy tiến trình đầu hàng, chạy tối đa q đơn vị thời gian; nếu chưa xong thì đưa lại cuối hàng, nếu xong thì rời hệ thống.

Yêu cầu

Tính thời điểm hoàn thành của từng tiến trình.

Input

• Dòng 1: n q.
• Dòng 2: n số t[i] là tổng thời gian CPU cần cho tiến trình i.

Output

In n thời điểm hoàn thành theo thứ tự ID 1..n.

Ràng buộc

• 1 <= n <= 5000
• 1 <= q <= 10^6
• 1 <= t[i] <= 10^6
• Tổng số lượt chạy ceil(t[i]/q) <= 2 * 10^6

Chấm điểm

Ví dụ 1

Input

3 2
3 1 4

Output

6 3 8

Giải thích. P1 chạy 2, P2 chạy 1 và xong lúc 3, P3 chạy 2, P1 chạy 1 và xong lúc 6, P3 xong lúc 8.

Ví dụ 2

Input

1 5
12

Output

12

Giải thích. Một tiến trình chạy ba lượt 5,5,2 và hoàn thành tại thời điểm 12.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.