Задача G. Спортивная ходьба ≡

Условие

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

Трасса для спортивной ходьбы представлена в виде ломаной на плоскости с вершинами в точках (x₁, y₁), (x₂, y₂), … (x_k, y_k). Ломаная может иметь самокасания и самопересечения. Судья с номером i неподвижно стоит в точке (cx_i, cy_i) и обозревает вокруг себя круг с радиусом r_i.

Таким образом, каждая точка трассы обозревается некоторым (возможно, нулевым) количеством судей. Напишите программу, которая по заданной трассе и положению судей определит длину участков, обозреваемых ровно m судьями для целых m от 0 до n.

Формат входного файла

Входной файл содержит целые числа n k. Далее содержится n троек целых чисел cx_i cy_i r_i, задающих положение судей. Далее содержится k пар целых чисел x_j y_j, задающих ломаную.

Формат выходного файла

Выходной файл должен содержать n + 1 число — ответы для 0, 1, …, n судей с точностью не менее 10^− 6.

Ограничения

1 ≤ n ≤ 1000;

2 ≤ k ≤ 1000;

Примеры тестов

2 4
3 0 2
6 0 2
0 0
4 0
6 0
10 0

3.000000
6.000000
1.000000