Bitə kömək#11518
Hər kəsə salam! Mənim adım Bit və mən Baytlandiya Respublikasının baş mühasibiyəm! Və yaxınlarda mənə aşağıdakı vəzifə tapşırıldı.
Baytlandiyada nazir var. Hər bir nazir hansısa bir naziri özünün ən yaxşı dostu hesab edir. Nazirlər çox qeyri-adi xalqdır: heç bir iki nazir eyni naziri öz ən yaxşı dostu hesab etmir, lakin ola bilər ki, hansısa nazir özünü ən yaxşı dostu hesab edir!
Yaxınlarda yeni bir əmr gəldi: bütün nazirlərə yeni maaşlar təyin etmək (cəmi yeni maaş). Lakin bir problem var: maaşlar mütləq bərabər deyil! Buna görə bəzi nazirlər narahat ola bilərlər. Yəni: -ci nazirin narahatlığı onun maaşı ilə ən yaxşı dostunun maaşı arasındakı mütləq fərqə bərabər olacaq.
Və mənim vəzifəm: maaşları elə bölüşdürməkdir ki, hər hansı bir nazirin maksimal narahatlığı mümkün qədər minimal olsun.
Amma bu vəzifə mənim üçün çox çətin oldu. Xahiş edirəm, mənə bu məsələnin həllində kömək edin, əks halda Baytlandiya dəhşətli iqtisadi böhrana qərq olacaq.
Girişin ilk sətiri n~(n \le 150) — nazirlərin ümumi sayını ehtiva edən bir ədəd ehtiva edir.
İkinci sətir müxtəlif ədəd ehtiva edir. -ci ədəd nömrəli nazirin ən yaxşı dostunun nömrəsidir.
Üçüncü sətir ədəd ehtiva edir, burada -ci ədəd növbəti maaşın ölçüsüdür. Hər bir maaşın ölçüsü 10^9-u keçmir.
Birinci sətirdə hər hansı bir nazirin minimal mümkün maksimal narahatlığını göstərin.
İkinci sətir boşluqla ayrılmış ədəd ehtiva etməlidir, burada -ci ədəd -ci nazirə təyin edilmiş maaşın ölçüsünü göstərir. Əgər bir neçə optimal maaş bölgüsü varsa, istənilən birini göstərin.
Nümunə 1
Nümunə 2
Nümunə 3