eolymp
bolt
Try our new interface for solving problems
Məsələlər

Керлинг

Керлинг

Zaman məhdudiyyəti 20 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Большое количество олимпийских трансляций из Ванкувера было посвящено керлингу, благодаря чему он приобрел большую популярность в России. Как известно, в керлинг играют гранитными камнями, пытаясь поставить их в дом ближе камней соперника. В официальных встречах все камни имеют одинаковые габариты. Но мало кто знает, что на тренировках используются камни разного диаметра. Это позволяет оттачивать различные аспекты мастерства спортсмена.

На тренировках применяется оборудование, которое может сверху фотографировать положение камней. Затем данные используются для анализа ошибок при бросках. Однако информация воспринимается лучше всего, если все броски отпечатаны на одной фотографии путем наложения. Вам необходимо по информации о расположении камней на льду получить такую фотографию.

Фотография представляет собой прямоугольник размером N*M клеток. Каждый камень на фотографии представляет собой круг с центром в некоторой клетке и радиусом, равным целому числу клеток. На фотографии все клетки (X, Y) i-ого круга, координаты центров которых удовлетворяют неравенству (X_0-X)^2 + (Y_0-Y)^2R^2, окрашивают в цвет C_i. Здесь X_0, Y_0 – координаты центра круга.

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

Giriş verilənləri

В первой строке записаны числа N, M, K (3N, M2500, 1K5000). Далее записано K строк с информацией о расположении камней на игровом поле - X_i, Y_i, R_i, C_i. (0X_i < N, 0Y_i < M, 1R < max(N,M) ). Цвет задается одним символом - буквой латинского алфавита. Большие и малые буквы следует различать.

Çıxış verilənləri

Необходимо вывести N строк по M символов – фотографию всех камней. Неокрашенную клетку следует обозначать точкой. Окрашенную клетку следует обозначать символом, соответствующим ее цвету.

Пример выходных данных приведен на рисунке:

Nümunə

Giriş verilənləri #1
20 30 3
5 6 8 a
10 23 5 b
17 17 10 c
Çıxış verilənləri #1
aaaaaaaaaaaaa.................
aaaaaaaaaaaaa.................
aaaaaaaaaaaaaa................
aaaaaaaaaaaaaa................
aaaaaaaaaaaaaa................
aaaaaaaaaaaaaaa........b......
aaaaaaaaaaaaaa......bbbbbbb...
aaaaaaaaaaaaaa...c.bbbbbbbbb..
aaaaaaaaaaaaacccccccccbbbbbb..
aaaaaaaaaaacccccccccccccbbbb..
aaaaaaaaaacccccccccccccccbbbb.
.aaaaaaaacccccccccccccccccbb..
...aaaaaacccccccccccccccccbb..
......a.cccccccccccccccccccb..
........ccccccccccccccccccc...
........ccccccccccccccccccc...
........ccccccccccccccccccc...
.......ccccccccccccccccccccc..
........ccccccccccccccccccc...
........ccccccccccccccccccc...
Müəllif Бирюков С.В.
Mənbə IV Открытая олимпиада ЮФУ