28298번 - 더 흔한 타일 색칠 문제 스페셜 저지

$N\times M$ 크기의 타일이 있다. 타일의 $i$행 $j$열에 해당하는 칸은 처음에 $d_{i,j}$ 색으로 색칠되어 있다. 타일의 색상은 하나의 알파벳 대문자로 표현된다.

주어진 타일을 $K\times K$ 크기의 작은 타일들로 겹치지 않게 나눴을 때, 나눠진 타일의 색상 배치가 전부 동일하도록 타일의 일부 칸을 골라 다시 색칠하고자 한다. 어떤 칸을 다시 색칠하는 데 사용할 수 있는 색상의 종류 또한 하나의 알파벳 대문자로 표현할 수 있는 색상 중 하나여야 한다.

최소 몇 개의 칸을 다시 색칠해야 하는지를 구하고, 이를 만족하는 타일의 색상 배치를 아무거나 하나 출력하라.

첫째 줄에 세 정수 $N$, $M$, $K$가 공백으로 구분되어 주어진다. $(1\le N,M,K\le 500;$ $N,M$은 $K$의 배수이다$)$

다음 $N$개의 줄에는 타일의 $i$행 색상 배치를 의미하는 길이 $M$의 문자열 $d_i$가 주어진다. $d_i$는 알파벳 대문자로만 이루어져 있다.

첫째 줄에는 다시 칠해야 하는 타일의 최소 개수를 출력한다.

다음 $N$개의 줄에는 새로 칠한 타일의 $i$행 색상 배치를 의미하는 길이 $M$의 문자열을 출력한다. 출력하는 문자열 역시 모두 알파벳 대문자로만 이루어져 있어야 한다.