You are given a table $a$ of size $n \times m$ consisting of the characters 'R', 'G', and 'B'. You are also given integers $c$ ($2 \le c \le 3$) and $q$, where $c$ is the number of distinct characters that can appear in the table. If $c$ is 2, only the characters 'R' and 'G' are available; if $c$ is 3, the characters 'R', 'G', and 'B' are available.

You need to change the values of at most $q$ elements of the table such that there are no pairs of side-adjacent cells that have the same value. Note that if $c = 2$, it is forbidden to use the character 'B' when changing the values of the table cells.

It is guaranteed that under the given constraints, there exists a way to change at most $q$ elements of the table such that there are no pairs of side-adjacent cells that have the same value.

Note that there is no "no additional constraints" block in this problem.

Input

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 100$) — the number of rows and columns of the table $a$, respectively.

The second line contains two integers $c$ ($2 \le c \le 3$) and $q$, which denote the number of available characters and the number of allowed changes in the table, respectively.

The next $n$ lines contain $m$ characters each — the elements of the table $a$. If $c = 2$, then $a_{ij} \in \{\text{'R'}, \text{'G'}\}$. If $c = 3$, then $a_{ij} \in \{\text{'R'}, \text{'G'}, \text{'B'}\}$.

Output

Output $n$ lines of $m$ characters each, describing the table after the changes have been made.

If there are multiple correct answers, you may output any of them.

Subtasks

1. (7 points): $n = 1, c = 3, q = \lfloor \frac{n \cdot m}{2} \rfloor$;
2. (7 points): $n = 1, c = 2, q = \lfloor \frac{n \cdot m}{2} \rfloor$;
3. (3 points): $c = 3, q = n \cdot m$;
4. (7 points): all rows of table $a$ are identical, $a[1][j] \neq a[1][j + 1]$ (for $1 \le j < m$), $c = 3, q = \lfloor \frac{n \cdot m}{2} \rfloor$;
5. (7 points): all rows of table $a$ are identical, $c = 3, q = \lfloor \frac{n \cdot m}{2} \rfloor$;
6. (13 points): $c = 3, q = \lfloor \frac{2 \cdot n \cdot m}{3} \rfloor$;
7. (19 points): $c = 3, n \le 5, m \le 100, q = \lfloor \frac{n \cdot m}{2} \rfloor$;
8. (17 points): $c = 2, q = \lfloor \frac{n \cdot m}{2} \rfloor$;
9. (20 points): $c = 3, q = \lfloor \frac{n \cdot m}{2} \rfloor$.

Examples

Input 1

3 3
3 4
RRR
RRR
RRR

Output 1

RGR
GRG
RGR

Input 2

3 2
2 3
RG
GG
GR

Output 2

RG
GR
RG