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

Автор:И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

Трасса для спортивной ходьбы представлена в виде ломаной на плоскости с вершинами в точках (x1, y1), (x2, y2), … (xk, yk). Ломаная может иметь самокасания и самопересечения. Судья с номером i неподвижно стоит в точке (cxi, cyi) и обозревает вокруг себя круг с радиусом ri.

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

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

Входной файл содержит целые числа n k. Далее содержится n троек целых чисел cxi cyi ri, задающих положение судей. Далее содержится k пар целых чисел xj yj, задающих ломаную.

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

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

Ограничения

1 ≤ n ≤ 1000;

2 ≤ k ≤ 1000;

1000 ≤ xj, yj, cxi, cyi ≤ 1000;

1 ≤ ri ≤ 1000;

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 4
3 0 2
6 0 2
0 0
4 0
6 0
10 0
3.000000
6.000000
1.000000

0.019s 0.004s 15