"Metro"#6081
Dovşan McRabbit, Rabbitville şəhərinin meri, şəhərin yeraltı metro sisteminə ehtiyacı olduğuna qərar verib. Sistem tək bir xəttdən ibarət olacaq və bu xətt Rabbitville-in bir tərəfindən birbaşa qarşı tərəfinə düz şəkildə gedəcək. Mer israr edir ki, xəttdə heç bir əyilmə olmasın.
Bundan əlavə, metro stansiyaları xətt boyunca dəqiq göstərilmiş bir neçə yerdə yerləşəcək. Hər stansiyanın, xətt boyunca, yerdə (tunelin üstündə və ya altında, amma istənilən halda tunellə eyni xəttdə olmaqla) bir küçə səviyyəsində girişi olacaq. Hər giriş, stansiyasından çox uzaq olmamalıdır: xətt boyu stansiya ilə girişi arasındakı məsafə ən çoxu ola bilər (lakin daha az da ola bilər, hətta də ola bilər).
McRabbita kömək edin ki, girişlərin yerləri elə seçilsin ki, ardıcıl istənilən iki stansiyanın girişləri arasındakı məsafələr bərabər olsun.
Həm metro stansiyalarını, həm də onların girişlərini tunel boyunca olan xətt üzərindəki nöqtələr kimi qəbul edirik. Birinci sətirdə iki tam ədəd var: — metro stansiyalarının sayı (2 \le n \le 1000) və — stansiya ilə girişi arasındakı maksimum icazəli məsafə (0 \le d \le 10\ 000).
İkinci sətirdə müxtəlif tam ədəd artan qaydada verilib, məxrajların modulu 10^9-dan böyük deyil. Bunlar xətt üzərindəki birinci, ikinci, ..., sonuncu stansiyanın koordinatlarıdır.
Birinci, ikinci, ..., sonuncu stansiyanın girişlərinin koordinatlarını göstərən tam ədəd çıxarın. Heç bir iki giriş eyni nöqtədə yerləşə bilməz. Bir neçə həll varsa, istənilən birini çıxarın. Tam həllər yoxdursa, 0 çıxarın.
Nümunə 1