Задача . Покраска холста

Радиоуправляемый робот умеет перемещаться по клетчатому полю размером \(n \times m\) (\(n\) строк и \(m\) столбцов) и красить клетки в один из четырех цветов (красный, зеленый, синий и белый). Будем обозначать клетку на пересечении \(i\)-й сверху строки и \(j\)-го слева столбца как \((i, j)\).

Робот выполняет команды пользователя, при этом перемещаясь по полю в соответствии с заданными настройками и ограничениями.

Настройки представляют собой матрицу \(S\) размера \(n \times m\), каждый элемент которой — либо \(\varnothing\), либо пара из направления (вправо, вверх, влево, вниз) и цвета. Если \(S_{i,j} = (d, c)\), то после того, как робот красит клетку \((i, j)\) в какой-либо цвет, он сразу же смещается на одну клетку в направлении \(d\) и красит ее в цвет \(c\). Если для новой покрашенной клетки \(S_{i',j'} \neq \varnothing\), процесс продолжается по тем же правилам.

Ограничения бывают двух типов:

1. ограничение на максимальное разрешенное число клеток цвета \(c\);

2. запрет наличия на поле квадрата \(2 \times 2\), покрашенного цветами \(\begin{pmatrix} c_{1,1} & c_{1,2} \\ c_{2,1} & c_{2,2} \end{pmatrix}\).

Пользователю доступны следующие команды для взаимодействия с роботом:

1. <<color \(i\) \(j\) \(c\)>> — закрасить клетку \((i, j)\) в цвет \(c\), после чего выполнять действия в соответствии с настройками; процесс останавливается, когда

   • очередное перемещение привело робота за границу поля;

   • очередное перемещение привело робота в клетку, которую он уже красил в процессе выполнения текущей команды;

   • для очередной клетки \(S_{i',j'} = \varnothing\);

   • с очередной покраской перестанет выполняться какое-то из ограничений.

   Обратите внимание, что если первая же покраска клетки \((i, j)\) в цвет \(c\) приводит к нарушению какого-то из ограничений, робот остановится сразу же, не покрасив ни одну клетку.

2. <<limit \(c\) \(x\)>> — выставить ограничение на максимальное число клеток цвета \(c\) в \(x\). Если в настоящий момент на поле уже больше \(x\) клеток цвета \(c\), команда игнорируется и ограничение не меняется. Для каждого цвета в каждый момент времени действует только последнее введенное на него ограничение на число клеток.

3. <<block \(c_{1,1}\) \(c_{1,2}\) \(c_{2,1}\) \(c_{2,2}\)>> — запретить появление квадратов \(2 \times 2\), раскрашенных цветами \(\begin{pmatrix} c_{1,1} & c_{1,2} \\ c_{2,1} & c_{2,2} \end{pmatrix}\). Если в настоящий момент на поле уже есть квадрат, раскрашенный таким образом, команда игнорируется и ограничение не добавляется.

4. <<allow \(c_{1,1}\) \(c_{1,2}\) \(c_{2,1}\) \(c_{2,2}\)>> — аналогично, отменить запрет на раскрашенные соответствующим образом квадраты \(2 \times 2\), если такой запрет сейчас есть.

5. <<settings \(i\) \(j\) \(d\) \(c\)>> — выставить настройки для клетки \((i, j)\) в значение \((d, c)\), где \(d\) — направление перемещения, а \(c\) — цвет, в который затем будет раскрашена клетка, в которую робот переместится.

6. <<settings \(i\) \(j\) none>> — выставить настройки для клетки \((i, j)\) в значение \(\varnothing\), соответствующее отсутствию перемещения после покраски клетки \((i, j)\).

Еще раз повторим, что робот никогда не красит одну и ту же клетку дважды во время исполнения одной команды, а также останавливается до момента первого нарушения какого-либо ограничения. Например, если \(S_{1,1} = (\rightarrow, \mathtt{red})\), \(S_{1,2} = (\downarrow, \mathtt{blue})\), \(S_{2,2} = (\leftarrow, \mathtt{green})\) и \(S_{2,1} = (\uparrow, \mathtt{red})\), то при поступлении команды <<color \(1\) \(1\) blue>>, робот покрасит \((1, 1)\) в синий, \((1, 2)\) в красный, \((2, 2)\) в синий и \((2, 1)\) в зеленый. Затем робот остановится, так как клетка \((1, 1)\) уже была покрашена при исполнении этой команды.

Изначально все настройки равны \(\varnothing\), никакие ограничения не введены, а все клетки поля покрашены в белый цвет. Вам дан список из \(q\) команд пользователя, которые были последовательно отправлены роботу. Выведите раскраску поля после применения всех этих команд.

Формат входных данных
В первой строке записано целое число \(t\) (\(1 \le t \le 1000\)) — число наборов входных данных в тесте.

В первой строке каждого набора данных даны три целых положительных числа \(n\), \(m\) и \(q\) — размеры поля и число команд. Гарантируется, что сумма \(n \cdot m \cdot q\) по всем наборам входных данных не превосходит \(10^5\).

В следующих \(q\) строках дано описание команд, посланных роботу в формате, описанном в условии. Направления задаются строками <<right>> (вправо), <<up>> (вверх), <<left>> (влево), <<down>> (вниз). Цвета задаются заглавными буквами ‘R’ (красный), ‘G’ (зеленый), ‘B’ (синий) и ‘W’ (белый).

Формат выходных данных
Для каждого набора входных данных выведите итоговую раскраску поля, полученную после обработки всех команд.

В первом примере из условия

1. Команда <<color 1 1 R>> красит \((1, 1)\) в красный, после чего из-за \(S_{1,1} = (\downarrow, \mathtt{red})\) клетка \((2, 1)\) тоже красится в красный, а из-за \(S_{2,1} = (\downarrow, \mathtt{red})\) затем и \((3, 1)\) красится в красный.

2. При выполнении <<color 2 1 G>> робот красит \((2, 1)\) в зеленый. \(S_{2,1}\) в этот момент уже равно \((\rightarrow, \mathtt{blue})\), поэтому после этого клетка \((2, 2)\) должна быть покрашена в синий, но это бы нарушило ограничение <<limit B 0>>, поэтому процесс останавливается до этого.

3. После этого поле выглядит как

   RW
   GW
   RW

4. Затем <<color 2 2 R>> должен покрасить \((2, 2)\) в красный, но это бы привело к получению квадрата с цветами RWGR, который запрещен, поэтому выполнение команды сразу останавливается.

5. Последняя команда покраски <<color 2 2 B>> отрабатывает корректно, так как до этого было разрешено иметь на поле не больше \(1\) синей клетки. После чего, в соответствии с \(S_{2,2} = (\uparrow, \mathtt{green})\), клетка \((1, 2)\) красится в зеленый.

6. Итоговый рисунок:

   RG
   GB
   RW

R G
G B
R W
W W W R
G R B R
W B B W