F. BerPaint
ограничение по времени на тест
5 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Обезьянка Анфиса разочаровалась в текстовых редакторах, потому что они недостаточно хороши, чтобы передать всю полноту переживаемых ею эмоций, поэтому она решила переключиться на графические редакторы. Открыв редактор BerPaint, она увидела белый прямоугольник размера W × H, на котором можно рисовать. Первым делом Анфиса освоила чертежный инструмент, позволяющий рисовать отрезки, и быстро набросала на этом прямоугольнике некоторое число отрезков черного цвета. Получившаяся картина показалась Анфисе недостаточно яркой, поэтому она обратила внимание на инструмент «Заливка», который позволяет указать точку в прямоугольнике для рисования и выбрать цвет, после чего вся область, имеющая тот же цвет, что и выбранная точка, и содержащая ее, полностью окрашивается в выбранный цвет. Применив заливку много раз в разных точках, Анфиса полностью выразила всю свою экспрессию и бросила рисование. От вас же требуется по информации о нарисованных отрезках и проведенных заливках определить для каждого цвета, какова суммарная площадь областей, окрашенных в этот цвет после всех заливок.

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

В первой строке заданы два целых числа W и H (3 ≤ W, H ≤ 104) — размеры изначально белой прямоугольной области для рисования. Во второй строке записано целое число n — количество черных отрезков (0 ≤ n ≤ 100). В следующих n строках описаны сами отрезки, каждый из которых задается координатами своих концов x1, y1, x2, y2 (0 < x1, x2 < W, 0 < y1, y2 < H). Все отрезки имеют ненулевую длину. В следующей строке задано число заливок m (0 ≤ m ≤ 100). Каждая из следующих m строк задает операцию заливки в виде «x y color», где (x, y) это координаты выбранной точки (0 < x < W, 0 < y < H), а color — строка из маленьких латинских букв длиной от 1 до 15 символов, задающая цвет. Изначально прямоугольник имеет цвет «white», а отрезки наносятся цветом «black». Координаты концов всех отрезков и координаты точек заливки целые.

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

Для каждого цвета, который присутствует на итоговой картинке, на отдельной строке выведите название этого цвета и суммарную площадь областей, окрашенных в этот цвет, с точностью 10 - 6. Цвета выдавайте в любом порядке.

Примеры
Входные данные
4 5
6
1 1 1 3
1 3 3 3
3 3 3 1
3 1 1 1
1 3 3 1
1 1 3 3
2
2 1 red
2 2 blue
Выходные данные
blue 0.00000000
white 20.00000000
Входные данные
5 5
5
1 1 2 2
2 2 4 2
4 2 4 4
4 4 2 4
2 4 2 2
2
3 3 black
3 3 green
Выходные данные
green 4.00000000
white 21.00000000
Входные данные
7 4
9
1 2 2 3
2 3 3 2
3 2 2 1
2 1 1 2
3 2 4 2
4 2 5 3
5 3 6 2
6 2 5 1
5 1 4 2
2
2 2 black
2 2 red
Выходные данные
red 2.00000000
white 26.00000000
Примечание

Изначально черные отрезки, которые нарисовала Анфиса, также могут быть окрашены, если какая-то из выбранных точек попадет на отрезок. Отрезки имеют нулевую площадь. Поэтому, если в итоговой картинке в какой-то цвет будут окрашены только лишь части отрезков, то площадь, окрашенная в этот цвет, равна 0.