Керлинг
Большое количество олимпийских трансляций из Ванкувера было посвящено керлингу, благодаря чему он приобрел большую популярность в России. Как известно, в керлинг играют гранитными камнями, пытаясь поставить их в дом ближе камней соперника. В официальных встречах все камни имеют одинаковые габариты. Но мало кто знает, что на тренировках используются камни разного диаметра. Это позволяет оттачивать различные аспекты мастерства спортсмена.
На тренировках применяется оборудование, которое может сверху фотографировать положение камней. Затем данные используются для анализа ошибок при бросках. Однако информация воспринимается лучше всего, если все броски отпечатаны на одной фотографии путем наложения. Вам необходимо по информации о расположении камней на льду получить такую фотографию.
Фотография представляет собой прямоугольник размером N*M клеток. Каждый камень на фотографии представляет собой круг с центром в некоторой клетке и радиусом, равным целому числу клеток. На фотографии все клетки (X, Y) i-ого круга, координаты центров которых удовлетворяют неравенству (X_0-X)^2 + (Y_0-Y)^2 ≤ R^2, окрашивают в цвет C_i. Здесь X_0, Y_0 – координаты центра круга.
Понятно, что после последовательного наложения изображений всех камней некоторые клетки могут быть окрашены несколько раз, в этом случае цветом клетки является последний цвет, в который она была окрашена. Другие клетки могут вообще остаться неокрашенными.
Входные данные
В первой строке записаны числа N, M, K (3 ≤ N, M ≤ 2500, 1 ≤ K ≤ 5000). Далее записано K строк с информацией о расположении камней на игровом поле - X_i, Y_i, R_i, C_i. (0 ≤ X_i < N, 0 ≤ Y_i < M, 1 ≤ R < max(N,M) ). Цвет задается одним символом - буквой латинского алфавита. Большие и малые буквы следует различать.
Выходные данные
Необходимо вывести N строк по M символов – фотографию всех камней. Неокрашенную клетку следует обозначать точкой. Окрашенную клетку следует обозначать символом, соответствующим ее цвету.
Пример выходных данных приведен на рисунке:
