More Common Tile Coloring

An $N\times M$ tile is given. The cell at row $i$, column $j$ is initially painted with color $d\_{i,j}$. Each color is a single uppercase English letter.

Split the tile into non-overlapping $K\times K$ small tiles. Repaint some cells so that every small tile has the same color layout. The color used to repaint any cell must also be a single uppercase English letter.

Find the minimum number of cells that must be repainted, and print any one tile layout that satisfies this.

The first line contains three integers $N$, $M$, and $K$ separated by spaces. $(1\le N,M,K\le 500;$ $N$ and $M$ are multiples of $K$.$)$

The next $N$ lines contain a string $d\_i$ of length $M$, which is row $i$ of the tile colors. $d\_i$ consists only of uppercase English letters.

The first line prints the minimum number of cells that must be repainted.

The next $N$ lines print the repainted tile, where line $i$ is a string of length $M$ for row $i$. The output strings also consist only of uppercase English letters.