Как же преобразился наш парк!

Идёт 2028 год. 20 лет назад парк выглядел совсем иначе, им почти никто не занимался, да ещё и вход был платным. А сейчас, помимо великолепных видов, фестивалей, вечеринок, уроков танцев, занятий йогой, развлечений для людей любых возрастов, тут начала развиваться новая инновационная система ухода за самим парком. Благодаря ей, через 10 лет он станет ещё более зелёным и красивым! Если, конечно, её правильно настроят.

Сейчас система выглядит следующим образом: На центральной площади расположен фонтан. Фонтан является плоским кругом на земле радиуса R (У всех точек фонтана координата z равна нолю). Центр этого фонтана является центром координат. В точке (0, 0, 1) (x, y, z координаты соответственно) находится дрон-база с дроном-садовником. Садовник имеет бак для поливочной воды, вместимостью M литров. Бак наполняется в любой точке фонтана. Каждому цветку, находящемуся в кашпо, необходим 1 литр воды для поливки. Считается, что для того, чтобы полить кашпо с цветком, дрону нужно прилететь в точку местонахождения этого кашпо. То есть считается, что размерами кашпо и технологией поливки цветка можно пренебречь.

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

Напомним, что дрон начинает свой путь с базы - с точки (0, 0, 1). С базы дрон вылетает с полным баком воды и летит к своей первой цели. Путь между двумя целями вычисляется, как расстояние между двумя точками в трёхмерном пространстве, т. е. \(p = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2 + (z_1 - z_2)^2}\).

Итоговый путь — это последовательность номеров кашпо с цветами. Если дрону надо заправиться водой, в последовательность надо вставить F(\(x_F\), \(y_F\) ), где (\(x_F\), \(y_F\), 0) — это координаты точки внутри или на границе фонтана, а сами \(x_F\), \(y_F\) целые числа. Для того, чтобы заправиться, дрону не обязательно быть пустым. Последовательность должна заканчиваться буквой B, говорящей о том, что дрон полил все цветы и летит на базу. Номера кашпо с цветами и терминальные символы друг от друга отделяются пробелом. Метка пополнения воды не должна содержать пробелов. То есть запись (F(2, 4)) не допустима, потому что в ней есть пробел после запятой. Если метка описана неправильно, выводится вердикт PE и весь тест получает 0 баллов.

Вам необходимо постараться минимизировать длину пути дрона, проходимого в процессе поливки.

В каждом тесте в первой строке находится число T — количество ситуаций.

Каждая ситуация описывается N + 1 строками. В первой строке находятся три числа N, R, M — количество кашпо с цветами, радиус фонтана и вместимость бака дрона соответственно. В остальных N строках по три числа — \(x_i\) , \(y_i\) , \(z_i\) координаты кашпо с номером i. Каждая ситуация в тесте оценивается независимо. Баллы за ситуацию начисляются по формуле max(0, 10 - ( anspart/ ansjury - 1) · 1.25), где ansjury — это длина кратчайшего пути для дрона, найденного жюри и участниками, а anspart — длина пути, найденного участником.

Если дрон пытается взять воду из точки не из фонтана, прилетает к цветку с пустым баком, прилетает на базу, не полив все цветы, или не прилетает обратно вовсе, за ситуацию ставится 0 баллов.

В тесте T = 10. Оценка за этот тест: 100 баллов. Ссылка на тест: тык

Пример

Входные данные

1
4 3 2
5 5 5
5 -5 5
-5 5 5
-5 -5 5

Выходные данные

1 2 F(0,-3) 4 3 B

Примечание

В примере дрон вылетает с базы, летит к кашпо 1, потом к кашпо 2, загружается водой в точке (0,−3,0), летит к кашпо 4, затем к кашпо 3 и завершает свой путь на базе.