32334번 - 자석 체스

문제

조선시대로 넘어온 세종이는 장기와 바둑에 질린 사람들에게 자석 체스를 알려주기로 했다.

자석 체스는 두 사람이 동일한 수의 자석을 나눠 가지고 $N \times N$ 크기의 보드에 번갈아 가면서 자신의 차례에 보드 위 빈 칸에 자석을 하나씩 놓는 게임이다.

보드 위 빈 칸에 자신이 가진 자석 중 하나를 자석끼리 서로 붙지 않게 놓아 모든 자석을 먼저 사용하는 사람이 승리한다. 단, 자석을 놓았을 때 붙은 자석이 있다면 새로 놓은 자석을 포함하여 붙은 자석을 모두 도로 가져가야 한다.

보드에서 $r$행 $c$열에 있는 자석의 위치는 $(r, c)$로 표현하며 보드의 가장 왼쪽 위 칸의 위치는 $(1, 1)$이다. 보드 위 어떤 자석의 위치가 $(r_1, c_1),ドル 새로 놓는 자석의 위치가 $(r_2, c_2)$라고 할 때 $\vert r_2 - r_1 \vert \le D$ 그리고 $\vert c_2 - c_1 \vert \le D$인 경우에 $(r_1, c_1)$에 있던 자석은 새로 놓은 자석의 위치로 붙는다.

게임을 하던 중 세종이에게는 드디어 1개의 자석이 남았고 이제 세종이의 차례가 시작됐다. 집중력이 떨어진 세종이를 위해 이번 차례에 놓을 수 있는 최선의 위치를 찾아보자.

입력

첫 번째 줄에 보드의 크기 $N$과 자석끼리 붙는 거리의 제한 $D$가 공백으로 구분되어 주어진다. $(3 \le N \le 1000;$ 1ドル \le D \le N)$

이후 $N$개의 줄에 걸쳐 보드의 각 행과 열의 상태가 주어지며 자석이 있는 칸은 1ドル,ドル 빈칸은 0ドル$으로 주어진다. $i$번째 줄의 $j$번째 수는 보드의 $i$행 $j$열에 자석이 있는 지 여부를 나타낸다.

초기에 주어지는 보드는 자석끼리 붙지 않는 상태만 입력으로 주어진다.

출력

첫 번째 줄에는 세종이가 이번 차례에 승리할 수 있다면 해당 위치를 출력한다. 세종이가 이번 차례에 승리할 수 있는 위치가 존재하지 않는다면 자석을 가장 적게 가져가는 위치를 출력한다. 위치는 행과 열을 공백으로 구분하여 출력한다.

두 번째 줄에는 세종이가 이번 차례에 승리할 수 있는 위치가 존재하지 않는다면 자석을 가장 적게 가져가는 개수를 출력한다.

출력할 수 있는 위치가 여러 곳이라면 행 번호가 작은 위치를 출력한다. 만약 행 번호가 같은 경우에는 열 번호가 더 작은 위치를 출력한다.

제한

힌트