Фраг­мент звёзд­но­го неба спро­еци­ро­ван на плос­кость с де­кар­то­вой си­сте­мой ко­ор­ди­нат. Учёный решил про­ве­сти кла­сте­ри­за­цию по­лу­чен­ных точек, яв­ля­ю­щих­ся изоб­ра­же­ни­я­ми звёзд, то есть раз­бить их мно­же­ство на N не­пе­ре­се­ка­ю­щих­ся не­пу­стых под­мно­жеств (кла­сте­ров), таких, что точки каж­до­го под­мно­же­ства лежат внут­ри пря­мо­уголь­ни­ка со сто­ро­на­ми дли­ной H и W, причём эти пря­мо­уголь­ни­ки между собой не пе­ре­се­ка­ют­ся. Сто­ро­ны пря­мо­уголь­ни­ков не обя­за­тель­но па­рал­лель­ны ко­ор­ди­нат­ным осям. Га­ран­ти­ру­ет­ся, что такое раз­би­е­ние су­ще­ству­ет и един­ствен­но для за­дан­ных раз­ме­ров пря­мо­уголь­ни­ков.

Будем на­зы­вать цен­тром кла­сте­ра точку (звез­ду) этого кла­сте­ра, сумма рас­сто­я­ний от ко­то­рой до всех осталь­ных его точек ми­ни­маль­на. Для каж­до­го кла­сте­ра га­ран­ти­ру­ет­ся един­ствен­ность его цен­тра. Рас­сто­я­ние между двумя точ­ка­ми на плос­ко­сти A(x₁, y₁) и B(x₂, y₂) вы­чис­ля­ет­ся по фор­му­ле:

Каж­дая звез­да по­ми­мо ко­ор­ди­нат на плос­кой карте ха­рак­те­ри­зу­ет­ся своим спек­траль­ным клас­сом и клас­сом све­ти­мо­сти. Спек­траль­ный класс опре­де­ля­ет цвет (ко­то­рый свя­зан с тем­пе­ра­ту­рой звез­ды) сле­ду­ю­щим об­ра­зом.

Каж­дый из спек­траль­ных клас­сов, в свою оче­редь, де­лит­ся на под­клас­сы от 0 до 9 в по­ряд­ке умень­ше­ния тем­пе­ра­ту­ры. Обо­зна­че­ние под­клас­са ста­вит­ся после обо­зна­че­ния спек­траль­но­го клас­са (на­при­мер, B2).

Класс све­ти­мо­сти звез­ды обо­зна­чим рим­ски­ми циф­ра­ми от I до VII.

В файле A хра­нит­ся ин­фор­ма­ция о точ­ках двух кла­сте­ров, где H  =  6,0 и W  =  5,5 для каж­до­го кла­сте­ра. В каж­дой стро­ке сна­ча­ла за­пи­са­на ин­фор­ма­ция о рас­по­ло­же­нии на карте одной звез­ды: ко­ор­ди­на­та x, затем ко­ор­ди­на­та y. Далее в той же стро­ке для звёзд клас­сов све­ти­мо­сти I–VI ука­зы­ва­ют­ся спек­траль­ный класс, под­класс и класс све­ти­мо­сти. Обо­зна­че­ния клас­сов ничем не раз­де­ля­ют­ся. Для звёзд клас­са све­ти­мо­сти VII (Белый кар­лик) обо­зна­че­ния спек­траль­но­го клас­са и под­клас­са в файле не ука­зы­ва­ют­ся. Из­вест­но, что ко­ли­че­ство точек не пре­вы­ша­ет 2000.

В файле Б хра­нят­ся ко­ор­ди­на­ты точек трёх кла­сте­ров, где H  =  6,0, W  =  5,5 для каж­до­го кла­сте­ра. Из­вест­но, что ко­ли­че­ство точек не пре­вы­ша­ет 10 000. Струк­ту­ра хра­не­ния ин­фор­ма­ции в файле Б ана­ло­гич­на струк­ту­ре в файле А.

Для файла А опре­де­ли­те ко­ор­ди­на­ты цен­тра каж­до­го кла­сте­ра, затем най­ди­те два числа: A_x и A_y  — абс­цис­су и ор­ди­на­ту крас­но­го ги­ган­та, бли­жай­ше­го к цен­тру кла­сте­ра, ко­то­рый со­дер­жит наи­мень­шее ко­ли­че­ство точек.

Для файла Б опре­де­ли­те ко­ор­ди­на­ты цен­тра каж­до­го кла­сте­ра, затем най­ди­те два числа: B₁  — рас­сто­я­ние между цен­тра­ми кла­сте­ров с наи­мень­шим и наи­боль­шим ко­ли­че­ством оран­же­вых ги­ган­тов и B₂  — наи­боль­шее рас­сто­я­ние между жёлтыми кар­ли­ка­ми од­но­го кла­сте­ра.

В от­ве­те за­пи­ши­те че­ты­ре числа: в пер­вой стро­ке  — сна­ча­ла целую часть аб­со­лют­ной ве­ли­чи­ны про­из­ве­де­ния A_x × 10 000, затем целую часть аб­со­лют­ной ве­ли­чи­ны про­из­ве­де­ния A_y × 10 000; во вто­рой стро­ке  — сна­ча­ла целую часть про­из­ве­де­ния B₁ × 10 000, затем целую часть про­из­ве­де­ния B₂ × 10 000.

При­мер ор­га­ни­за­ции дан­ных в одном из ис­ход­ных фай­лов для слу­чая четырёх звёзд

5,01788 8,32466 G2V

4,289251 6,955186 VII

4,619358 5,524697 B7V

6,91934 20,425391 G2V

Вни­ма­ние! При­мер при­ведён в ил­лю­стра­тив­ных целях для про­из­воль­ных зна­че­ний, не име­ю­щих от­но­ше­ния к за­да­нию. Для вы­пол­не­ния за­да­ния ис­поль­зуй­те дан­ные из при­ла­га­е­мых фай­лов.

Ответ: