Рудольф немного устал от математики и решил отвлечься. В закромах своего чердака он нашёл старую раскраску, которая оказалась весьма необычной.
Каждая страница раскраски представляет собой прямоугольную сетку размера m × n. Левый верхний угол сетки имеет координаты (0; 0), ось Ox направлена слева направо, ось Oy — сверху вниз. А на обратной стороне страницы напечатана инструкция в виде последовательности прямоугольных областей и цветов, в которые надо их покрасить.
Путём нехитрых подсчётов Рудольф выяснил, что в инструкциях по раскрашиванию фигурируют ровно p цветов. Недолго думая, он разыскал нужные краски и приступил к работе.
В процессе раскрашивания Рудольф заметил, что некоторые области, приведённые в инструкции, пересекаются. И если перемешать краски двух цветов, то в результате получится некоторый новый цвет. На последней странице раскраски Рудольф обнаружил палитру, которая для любой пары цветов позволяет определить, какой цвет получится в результате их перемешивания.
Рудольф ничего не смог поделать со своей тягой к автоматизации. Ему стало интересно, как реализовать программу, раскрашивающую прямоугольную сетку по имеющейся инструкции и карте соответствия цветов.
Гарантируется, что результат работы Рудольфа не зависит от порядка, в котором он будет закрашивать области.
Первая строка содержит целые числа n и m (1 ≤ n, m ≤ 2000) — количество столбцов и строк прямоугольной сетки раскраски.
Вторая строка содержит целое число p (1 ≤ p ≤ 26) — количество цветов.
Следующие строки описывают результаты перемешивания всех возможных пар цветов. Каждая из этих строк содержит символы cai, cbi и cri (
) — идентификаторы двух перемешиваемых цветов и результирующего цвета соответственно. Гарантируется, что в описании по одному разу присутствует каждая пара цветов.
Следующая строка содержит целое число k (0 ≤ k ≤ 1000) — количество прямоугольных областей в инструкции по раскрашиванию.
Следующие k строк описывают инструкцию по раскрашиванию. Каждая из них содержит целые числа x1, y1, x2, y2, а также символ cj (0 ≤ x1 ≤ x2 ≤ n, 0 ≤ y1 ≤ y2 ≤ m, 
) — координаты левого верхнего и правого нижнего углов прямоугольной области и идентификатор цвета, которым нужно закрасить данную прямоугольную область, соответственно. Гарантируется, что в инструкции используются только те цвета, которые есть в палитре.
Выведите m строк по n символов. Каждый символ должен соответствовать результирующему цвету клетки прямоугольной сетки, соответствующей позиции символа.
Если в результате на сетке останутся неокрашенные области, в соответствующих позициях выведите символ «-». Изначально сетка не окрашена.
2 3
2
a b a
a a b
b b b
3
0 0 2 3 b
1 1 2 2 a
1 1 2 3 a
bb
bb
ba
3 3
4
y b g
c c c
b g c
c g g
b c b
y y c
g y b
y c y
b b y
g g y
3
1 2 3 3 g
1 0 3 2 c
1 1 2 2 g
-cc
-gc
-gg
В первом примере необходимо раскрасить сетку, состоящую из двух столбцов и трёх строк. В распоряжении имеются два цвета и палитра, состоящая из трёх правил смешивания цветов. Последовательность раскраски сетки показана на рисунке.
| 2017 II Интеллектуальная олимпиада ПФО |
|---|
| Закончено |
