Рассматриваются звёзды, изображения которых зафиксированы на фотографии участка звёздного неба, спроецированного на плоскость с декартовой системой координат.

Каждая звезда обладает следующими характеристиками: декартовы координаты x и y, радиус r и эффективная температура поверхности T (выраженные в относительных единицах — радиусах и температурах Солнца соответственно), а также признак, характеризующий её спектральный класс, обозначаемый числами от I до VII в римской системе счисления.

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

Будем называть центром кластера такую его звезду, для которой сумма модулей разности светимостей со всеми остальными звёздами этого кластера минимальна.

Если таких звёзд несколько, центром кластера считается та из них, у которой светимость наибольшая.

В каждой строке текстового файла хранится информация об одной звезде: координаты x и y, радиус r, температура T и признак.

Значения даны в одинаковых для всех звёзд единицах измерения, обозначения единиц измерения в файле не приводятся.

Значения в строке разделяются одним или несколькими пробелами и/или символами табуляции.

Количество строк в файле не превышает 10~000.

Абсолютная величина каждого числового значения не превышает 100,0.

Известно, что все описанные в файле звёзды подразделяются ровно на 4 кластера (K=4) с R=2,0 для каждого.

Для каждого кластера определите его центр, затем найдите два числа: Q1 — наименьшее евклидово расстояние между звёздами одного кластера, имеющими признак IV, и Q2 — минимальное значение светимости для центра кластера.

В ответе запишите два числа: сначала целую часть произведения Q1 × 10 000, затем целую часть произведения Q2 × 10 000.

Для справки

Светимость L звезды радиуса r и температуры поверхности T (упрощённый закон Стефана—Больцмана в относительных единицах) вычисляется по формуле:

L = r² · T⁴

Евклидово расстояние между двумя точками на плоскости A(x1, y1) и B(x2, y2) вычисляется по формуле:

d(A, B) = √((x2 - x1)² + (y2 - y1)²)

Типовой пример организации данных во входном файле

Три строки файла для трёх звёзд:

0,67   -2,14   1,2    0,9     V
3,14    7,22   2,0    1,3     IV
1,33    5,56   0,80   1,10    IV

Для звезды из первой строки примера светимость равна 0,944784.

Типовой пример имеет иллюстративный характер.

Для выполнения задания используйте данные из прилагаемого файла.