로고마크
시간 제한3초메모리 제한1024 MB
격자에서 사용되는 칸을 빨간색 K칸과 흰색으로 나누어, 빨간 영역과 흰 영역이 모두 선대칭이 되도록 색칠합니다.
문제
다가오는 20XX년에 국제정보학 축제(International Omatsuri in Informatics)가 일본에서 열리게 되었다. 그래서 당신이 이 축제의 로고마크를 만들게 되었다.
국제정보학 축제의 로고마크는 매번 정해진 그림을 바탕으로 만든다. 이 그림은 가로 W칸, 세로 H칸으로 늘어선 정사각형 칸 중 일부로 이루어진다. 이번에는 이 그림을 일본 국기의 색인 빨강과 흰색으로 나누어 칠한다. 칠하는 작업이 복잡해지지 않도록, 한 칸에는 한 가지 색만 쓸 수 있다.
어떻게 칠하면 좋을지 정하려고, 당신은 아는 디자이너에게 조언을 구했다. 그는 빨갛게 칠한 영역과 흰색으로 칠한 영역이 모두 선대칭 도형인 디자인이 바람직하다고 했다. 또한 색의 균형을 생각하면 빨갛게 칠하는 칸은 K개로 하는 것이 좋다고 했다. 디자이너는 이 조건을 만족하는 칠하는 방법을 알려 주지 않았으므로, 당신이 직접 칠하는 방법을 구해야 한다. 그림과 K의 값이 주어졌을 때, 조건을 만족하는 칠하는 방법을 하나 구하는 프로그램을 작성하라.
입력
입력의 첫 줄에는 공백으로 구분된 세 정수 W, H, K가 주어진다(, , ). 각각 그림의 가로 너비, 세로 너비, 빨갛게 칠할 칸의 수를 나타낸다.
이어지는 H줄은 그림 데이터를 나타낸다. i+1번째 줄()에는 공백으로 구분된 0 또는 1이 W개 주어진다. i+1번째 줄의 j번째 수()가 1이면 위에서 i번째, 왼쪽에서 j번째 칸이 그림에 쓰인다는 뜻이고, 0이면 쓰이지 않는다는 뜻이다.
그림에는 반드시 2개 이상의 칸이 쓰인다. K는 그림에 쓰인 칸의 수보다 작다고 보장된다.
출력
표준 출력에 칠하는 방법을 나타내는 정수를 공백으로 구분하여 W개씩, H줄에 걸쳐 출력하라. i번째 줄의 j번째 정수가 1이면 위에서 i번째, 왼쪽에서 j번째 칸을 빨갛게 칠한다는 뜻이고, 2이면 흰색으로 칠한다는 뜻이다. 그림에 쓰이지 않는 칸은 0을 출력한다.
힌트
이 출력은 아래 칠하는 방법에 해당한다. 회색 칸은 빨갛게 칠하고, 흰 칸은 흰색으로 칠한다. 파선과 점선은 각각 빨간 영역과 흰 영역의 대칭축이다.
다음 칠하는 방법은 조건을 만족하지 않는다.
 |  |
| 빨간 영역이 선대칭이 아니다 | 빨갛게 칠한 칸의 수가 2가 아니다 |