Условие

В поселке X стоят домашние Wi-Fi роутеры. Для каждого роутера известны координаты (x, y), радиус покрытия r и номер провайдера p.

Агент Роскомнадзора едет на велосипеде со скоростью V и может начать маршрут из любой точки плоскости. Проверка одного провайдера в одной точке занимает D секунд. Если в выбранной точке доступны сети сразу нескольких провайдеров, их можно проверять последовательно без перемещения.

Нужно вывести сам маршрут: точки остановок и список провайдеров, которых агент проверяет в каждой точке. По этому маршруту система сама посчитает суммарное время. Чем меньше время, тем лучше решение.

Формат ввода

Первая строка содержит N, K, V и D.
Следующие N строк содержат x_i, y_i, r_i, p_i.
Во встроенных тестах все числа во входе целые и положительные: координаты x_i и y_i, радиусы r_i, скорость V и задержка D. Номера провайдеров во встроенных тестах идут подряд от 1 до K без повторов.
Во встроенных примерах число провайдеров K меняется от 3 до 30.

Формат вывода

В первой строке выведите число остановок M.
Каждая из следующих M строк должна иметь вид:
`x y c p_1 p_2 ... p_c`
Здесь `(x, y)` — точка остановки, `c` — сколько провайдеров агент проверяет в этой точке, а затем перечислены их номера.
Допускается `c = 0`: это чистая точка замера без новой проверки провайдера.

Система проверит корректность покрытия, убедится, что каждый роутер накрыт хотя бы одной точкой замера, и сама посчитает итоговое время маршрута.

Примечания

Открытых тестов 10, скрытых тестов тоже 10. Во встроенном наборе число провайдеров меняется от 3 до 30, все числа во входе целые и положительные, номера провайдеров идут подряд от 1 до K без повторов, точки стоят не по простой сетке, а почти случайно, и радиусы покрытия заметно различаются. Важна не только корректность покрытия, но и качество маршрута: платформа автоматически сравнивает суммарное время с худшими найденными решениями на каждом тесте. Каждый роутер должен быть накрыт хотя бы одной точкой замера. Повторно проверять одного и того же провайдера нельзя, но разрешены дополнительные точки замера с `c = 0`.

3 3 2 2
32 8 10 1
3 3 34 2
31 10 17 3

1
31 10 3 1 2 3