지뢰 제거

한 도시에 지뢰가 묻혀 있을 수 있는 칸들이 있다. 도시에 지뢰 제거용 폭탄을 설치해 터뜨려서, 지뢰가 있을 수 있는 모든 칸을 적어도 한 번씩 폭파해야 한다.

도시는 격자로 표현된다. 0은 지뢰가 있을 수 있고 폭탄도 설치할 수 있는 빈칸, 1은 건물, 2는 폭발에도 부서지지 않는 벽이다. 폭탄은 빈칸에만 설치할 수 있으며, 폭발이 건물을 건드리면 안 된다.

폭탄에는 길이 K가 있다. 폭탄이 터지면 폭탄이 놓인 칸과 그 칸에서 위, 아래, 왼쪽, 오른쪽으로 각각 최대 K칸까지 폭발이 퍼진다. 단, 한 방향으로 퍼지던 폭발이 벽을 만나면 그 방향으로는 더 이상 진행하지 않는다.

도시의 모양과 폭탄의 길이가 주어질 때, 지뢰가 있을 수 있는 모든 칸을 폭파하도록 폭탄을 설치한 위치들을 출력하라.

첫째 줄에 두 자연수 N과 M이 주어진다. N은 도시의 세로 칸 수, M은 가로 칸 수이다.

다음 N개의 줄에는 도시의 각 칸을 나타내는 정수 M개가 주어진다. 각 정수는 0, 1, 2 중 하나이다.

마지막 줄에는 폭탄의 길이 K가 주어진다.

제한은 다음과 같다.

• 1 <= N <= 100
• 1 <= M <= 100
• 0 <= K <= 100

첫째 줄에 설치해 터뜨릴 폭탄의 개수 X를 출력한다.

다음 X개의 줄에는 각 폭탄을 설치할 위치를 한 줄에 하나씩 출력한다. 위치는 행 열 형식으로 출력하며, 행과 열은 1부터 시작한다.

출력한 모든 폭탄은 빈칸에 설치되어야 하고, 어떤 폭탄의 폭발도 건물을 건드리면 안 된다. 또한 모든 0 칸은 적어도 한 폭탄의 폭발 범위에 포함되어야 한다.