P12556

题目描述

给定一个大小为 $n \times m$ 的表格 $a$，其中包含符号 $\tt{R}$、$\tt{G}$、$\tt{B}$。

同时给定整数 $c$（$2 \leq c \leq 3$）和 $q$，其中 $c$ 表示表格中可能出现的不同符号的数量。如果 $c$ 等于 $2$，则表格中仅允许出现符号 $\tt{R}$ 和 $\tt{G}$；如果 $c$ 等于 $3$，则允许出现符号 $\tt{R}$、$\tt{G}$、$\tt{B}$。

你需要修改表格中最多 $q$ 个元素的值，使得不存在相邻单元格的值相同。注意，如果 $c=2$，则禁止在修改表格单元格时使用符号 $\tt{B}$。

题目保证在给定的约束条件下，存在一种方法可以通过修改最多 $q$ 个元素的值，使得表格中不存在相邻单元格的值相同。

注意：题目的各个子任务中，不存在“没有额外的约束条件”这句表述。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 100$），分别表示表格 $a$ 的行数和列数。

第二行包含两个整数 $c$（$2 \leq c \leq 3$）和 $q$，分别表示可用符号的数量和允许修改表格的次数。

接下来的 $n$ 行，每行包含 $m$ 个符号，表示表格 $a$ 的元素。如果 $c=2$，则 $a_{ij} \in \{\tt{R}, \tt{G}\}$；如果 $c=3$，则 $a_{ij} \in \{\tt{R}, \tt{G}, \tt{B}\}$。

输出格式

输出 $n$ 行，每行包含 $m$ 个符号，表示修改后的表格。

如果有多个正确答案，输出任意一个均可。

输入输出样例 #1

输入 #1

3 3
3 4
RRR
RRR
RRR

输出 #1

RGR
GRG
RGR

输入输出样例 #2

输入 #2

3 2
2 3
RG
GG
GR

输出 #2

RG
GR
RG

说明/提示

评分标准

• （$7$ 分）：$n = 1$，$c = 3$，$q = \lfloor \frac{n \cdot m}{2} \rfloor$；
• （$7$ 分）：$n = 1$，$c = 2$，$q = \lfloor \frac{n \cdot m}{2} \rfloor$；
• （$3$ 分）：$c = 3$，$q = n \cdot m$；
• （$7$ 分）：表格 $a$ 的所有行相同，$a[1][j] \neq a[1][j+1]$（对于 $1 \leq j < m$），$c = 3$，$q = \lfloor \frac{n \cdot m}{2} \rfloor$；
• （$7$ 分）：表格 $a$ 的所有行相同，$c = 3$，$q = \lfloor \frac{n \cdot m}{2} \rfloor$；
• （$13$ 分）：$c = 3$，$q = \lfloor \frac{2 \cdot n \cdot m}{3} \rfloor$；
• （$19$ 分）：$c = 3$，$n \leq 5$，$m \leq 100$，$q = \lfloor \frac{n \cdot m}{2} \rfloor$；
• （$17$ 分）：$c = 2$，$q = \lfloor \frac{n \cdot m}{2} \rfloor$；
• （$20$ 分）：$c = 3$，$q = \lfloor \frac{n \cdot m}{2} \rfloor$。