{"problem":{"name":"G. Рудольф и раскраска","description":{"content":"Рудольф немного устал от математики и решил отвлечься. В закромах своего чердака он нашёл старую раскраску, которая оказалась весьма необычной. Каждая страница раскраски представляет собой прямоуголь","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10132G"},"statements":[{"statement_type":"Markdown","content":"Рудольф немного устал от математики и решил отвлечься. В закромах своего чердака он нашёл старую раскраску, которая оказалась весьма необычной.\n\nКаждая страница раскраски представляет собой прямоугольную сетку размера m × n. Левый верхний угол сетки имеет координаты (0; 0), ось Ox направлена слева направо, ось Oy — сверху вниз. А на обратной стороне страницы напечатана инструкция в виде последовательности прямоугольных областей и цветов, в которые надо их покрасить.\n\nПутём нехитрых подсчётов Рудольф выяснил, что в инструкциях по раскрашиванию фигурируют ровно p цветов. Недолго думая, он разыскал нужные краски и приступил к работе.\n\nВ процессе раскрашивания Рудольф заметил, что некоторые области, приведённые в инструкции, пересекаются. И если перемешать краски двух цветов, то в результате получится некоторый новый цвет. На последней странице раскраски Рудольф обнаружил палитру, которая для любой пары цветов позволяет определить, какой цвет получится в результате их перемешивания. \n\nРудольф ничего не смог поделать со своей тягой к автоматизации. Ему стало интересно, как реализовать программу, раскрашивающую прямоугольную сетку по имеющейся инструкции и карте соответствия цветов. \n\nГарантируется, что результат работы Рудольфа *не зависит* от порядка, в котором он будет закрашивать области.\n\nПервая строка содержит целые числа n и m (1 ≤ n, m ≤ 2000) — количество столбцов и строк прямоугольной сетки раскраски.\n\nВторая строка содержит целое число p (1 ≤ p ≤ 26) — количество цветов.\n\nСледующие строки описывают результаты перемешивания всех возможных пар цветов. Каждая из этих строк содержит символы cai, cbi и cri () — идентификаторы двух перемешиваемых цветов и результирующего цвета соответственно. Гарантируется, что в описании по одному разу присутствует каждая пара цветов.\n\nСледующая строка содержит целое число k (0 ≤ k ≤ 1000) — количество прямоугольных областей в инструкции по раскрашиванию.\n\nСледующие k строк описывают инструкцию по раскрашиванию. Каждая из них содержит целые числа x1, y1, x2, y2, а также символ cj (0 ≤ x1 ≤ x2 ≤ n, 0 ≤ y1 ≤ y2 ≤ m, ) — координаты левого верхнего и правого нижнего углов прямоугольной области и идентификатор цвета, которым нужно закрасить данную прямоугольную область, соответственно. Гарантируется, что в инструкции используются только те цвета, которые есть в палитре.\n\nВыведите m строк по n символов. Каждый символ должен соответствовать результирующему цвету клетки прямоугольной сетки, соответствующей позиции символа.\n\nЕсли в результате на сетке останутся неокрашенные области, в соответствующих позициях выведите символ «_-_». Изначально сетка не окрашена.\n\nВ первом примере необходимо раскрасить сетку, состоящую из двух столбцов и трёх строк. В распоряжении имеются два цвета и палитра, состоящая из трёх правил смешивания цветов. Последовательность раскраски сетки показана на рисунке.\n\n## Входные Данные\n\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, ) — координаты левого верхнего и правого нижнего углов прямоугольной области и идентификатор цвета, которым нужно закрасить данную прямоугольную область, соответственно. Гарантируется, что в инструкции используются только те цвета, которые есть в палитре.\n\n## Выходные Данные\n\nВыведите m строк по n символов. Каждый символ должен соответствовать результирующему цвету клетки прямоугольной сетки, соответствующей позиции символа.Если в результате на сетке останутся неокрашенные области, в соответствующих позициях выведите символ «_-_». Изначально сетка не окрашена.\n\n## Примеры\n\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\n\n## Примечание\n\nВ первом примере необходимо раскрасить сетку, состоящую из двух столбцов и трёх строк. В распоряжении имеются два цвета и палитра, состоящая из трёх правил смешивания цветов. Последовательность раскраски сетки показана на рисунке.  \n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of columns and rows of the grid, respectively.  \nLet $ p \\in \\mathbb{Z}^+ $ denote the number of distinct colors, labeled by distinct lowercase letters $ c \\in \\Sigma $, where $ |\\Sigma| = p $.  \nLet $ \\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 $.  \nLet $ k \\in \\mathbb{Z}_{\\geq 0} $ denote the number of rectangular instructions.  \nFor 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 $.\n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 2000 $  \n2. $ 1 \\leq p \\leq 26 $  \n3. $ 0 \\leq k \\leq 1000 $  \n4. $ \\oplus $ is commutative and associative (implied by \"result does not depend on order\").  \n5. Each color in instructions is from $ \\Sigma $.  \n6. Initially, all grid cells are uncolored (denoted by \"_-_\").\n\n**Objective**  \nDefine the grid $ G: \\{0, \\dots, m-1\\} \\times \\{0, \\dots, n-1\\} \\to \\Sigma \\cup \\{ \\text{\"_-_\"} \\} $, where each cell $ (y, x) $ starts uncolored.  \nProcess each instruction $ i $ in arbitrary order: for all $ (y, x) \\in R_i $, update  \n$$\nG(y, x) = \n\\begin{cases}\nc_i & \\text{if } G(y, x) = \\text{\"_-_\"} \\\\\nG(y, x) \\oplus c_i & \\text{otherwise}\n\\end{cases}\n$$  \nOutput $ m $ lines, each containing $ n $ characters: the final color of each cell $ (y, x) $, or \"_-_\" if uncolored.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10132G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}