Perfect Marching Formation

Class A plans to achieve a great result in the school marching competition by arranging its squad in a perfect square formation. They define a perfect formation as one in which, for every person, the number of boys in the four adjacent directions (up, down, left, right) is even.

You are given the current formation of Class A as an n × n square. Each cell is either a girl or a boy. A girl is denoted by G and a boy by B. The only allowed operation is to change a girl into a boy. Your task is to perform as few changes as possible so that the resulting formation becomes perfect.

The parity condition for every cell (i,j) can be written in \( \LaTeX \) as follows:

\[ F_{i-1,j} + F_{i+1,j} + F_{i,j-1} + F_{i,j+1} \equiv 0 \pmod{2}, \] where

• \( F_{i,j} = 1 \) if the cell \((i,j)\) is a boy (either originally or after a change), and \( F_{i,j} = 0 \) if it remains a girl.
• If a neighbor is out of bounds, it is considered as contributing 0.

Note that if a cell originally contains a boy (B), it must remain a boy.

inputFormat

The first line contains a positive integer n (the size of the square formation).

Each of the next n lines contains n characters separated by spaces. Each character is either G (girl) or B (boy). For cells originally containing a boy, no change is allowed.

outputFormat

On the first line, output the minimum number of changes (i.e. the number of girls changed to boys) needed to obtain a perfect formation.

Then output the resulting n × n formation in the same format as the input. Each cell should be represented by B (for boy) or G (for girl). Note that if a girl is changed, its output becomes B.

sample

1
G

0
G