Рудольф немного устал от математики и решил отвлечься. В закромах своего чердака он нашёл старую раскраску, которая оказалась весьма необычной.
Каждая страница раскраски представляет собой прямоугольную сетку размера 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 символов. Каждый символ должен соответствовать результирующему цвету клетки прямоугольной сетки, соответствующей позиции символа.
Если в результате на сетке останутся неокрашенные области, в соответствующих позициях выведите символ «_-_». Изначально сетка не окрашена.
В первом примере необходимо раскрасить сетку, состоящую из двух столбцов и трёх строк. В распоряжении имеются два цвета и палитра, состоящая из трёх правил смешивания цветов. Последовательность раскраски сетки показана на рисунке.
## Входные Данные
Первая строка содержит целые числа 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 32a b aa a bb b b30 0 2 3 b1 1 2 2 a1 1 2 3 aВыходные данныеbbbbbaВходные данные3 34y b gc c cb g cc g gb c by y cg y by c yb b yg g y31 2 3 3 g1 0 3 2 c1 1 2 2 gВыходные данные-cc-gc-gg
## Примечание
В первом примере необходимо раскрасить сетку, состоящую из двух столбцов и трёх строк. В распоряжении имеются два цвета и палитра, состоящая из трёх правил смешивания цветов. Последовательность раскраски сетки показана на рисунке.
[samples]
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ denote the number of columns and rows of the grid, respectively.
Let $ p \in \mathbb{Z}^+ $ denote the number of distinct colors, labeled by distinct lowercase letters $ c \in \Sigma $, where $ |\Sigma| = p $.
Let $ \oplus : \Sigma \times \Sigma \to \Sigma $ be the color mixing function, defined for all unordered pairs $ (c_i, c_j) $ by given triples $ (c_i, c_j, c_k) $ such that $ c_i \oplus c_j = c_k $.
Let $ k \in \mathbb{Z}_{\geq 0} $ denote the number of rectangular instructions.
For each instruction $ i \in \{1, \dots, k\} $, let $ R_i = [x_{1,i}, x_{2,i}] \times [y_{1,i}, y_{2,i}] $ be a rectangular region with $ 0 \leq x_{1,i} \leq x_{2,i} \leq n $, $ 0 \leq y_{1,i} \leq y_{2,i} \leq m $, and color $ c_i \in \Sigma $.
**Constraints**
1. $ 1 \leq n, m \leq 2000 $
2. $ 1 \leq p \leq 26 $
3. $ 0 \leq k \leq 1000 $
4. $ \oplus $ is commutative and associative (implied by "result does not depend on order").
5. Each color in instructions is from $ \Sigma $.
6. Initially, all grid cells are uncolored (denoted by "_-_").
**Objective**
Define the grid $ G: \{0, \dots, m-1\} \times \{0, \dots, n-1\} \to \Sigma \cup \{ \text{"_-_"} \} $, where each cell $ (y, x) $ starts uncolored.
Process each instruction $ i $ in arbitrary order: for all $ (y, x) \in R_i $, update
$$
G(y, x) =
\begin{cases}
c_i & \text{if } G(y, x) = \text{"_-_"} \\
G(y, x) \oplus c_i & \text{otherwise}
\end{cases}
$$
Output $ m $ lines, each containing $ n $ characters: the final color of each cell $ (y, x) $, or "_-_" if uncolored.