Có \(N\) học sinh đứng trên một trục số. Học sinh được đánh số từ \(1\) đến \(N\) và phải đứng theo thứ tự từ trái sang phải; mọi vị trí đều là số nguyên.

Gọi \(B_i\) là vị trí của học sinh \(i\). Với mỗi \(i\), học sinh \(i\) không được đứng bên phải \(A_i\), tức là \(B_i \le A_i\). Hai học sinh liên tiếp phải cách nhau ít nhất \(K\), tức là \(B_{i+1} - B_i \ge K\). Khi \(K = 0\), nhiều học sinh có thể đứng cùng một vị trí.

Mọi \(B_i\) phải là số nguyên nhưng không có cận dưới; vị trí âm vẫn được phép.

Hãy tìm một dãy \([B_1, B_2, \ldots, B_N]\) thỏa các điều kiện trên và làm lớn nhất có thể giá trị \(B_1\). Nếu có nhiều dãy tối ưu, in ra bất kỳ dãy nào. Có thể chứng minh luôn tồn tại ít nhất một dãy hợp lệ.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(N\), \(K\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\).

Dữ liệu ra

In ra \(N\) số nguyên \(B_1, B_2, \ldots, B_N\). Dãy phải hợp lệ và \(B_1\) phải lớn nhất có thể.

Ràng buộc

• \(1 \le N \le 100\).
• \(0 \le K \le 10\).
• \(1 \le A_i \le 100\).

Phân nhóm

• Nhóm 1 (25 điểm): \(A_{i+1} - A_i \ge K\) với mọi \(1 \le i < N\).
• Nhóm 2 (35 điểm): \(K = 0\).
• Nhóm 3 (30 điểm): tồn tại một dãy hợp lệ có \(0 \le B_1 \le 100\).
• Nhóm 4 (10 điểm): Không có ràng buộc bổ sung.

Ví dụ

5 2
1 4 10 9 13

1 4 6 9 12

4 0
5 2 7 3

2 2 3 3

4 3
2 1 5 9

-2 1 5 8

Nguồn

KOI 2026 Round 2, problem Distancing. Tài liệu, dữ liệu chấm và mã nguồn mẫu từ Korean Olympiad in Informatics, phát hành theo CC BY-NC-SA 4.0.