Mine Removal

Some cells in a city may contain mines. You must place and detonate mine-removal bombs so that every cell that may contain a mine is blasted at least once.

The city is represented as a grid. A 0 is an empty cell where a mine may exist and where a bomb may be placed, a 1 is a building, and a 2 is a wall that is not destroyed by explosions. Bombs may be placed only on empty cells, and an explosion must not touch any building.

Each bomb has a length K. When a bomb explodes, it affects its own cell and up to K cells in each of the four directions: up, down, left, and right. If the blast moving in one direction reaches a wall, it stops in that direction and does not continue beyond the wall.

Given the city and the bomb length, output positions where bombs should be placed so that every possible mine cell is blasted.

The first line contains two natural numbers N and M. N is the number of rows in the city, and M is the number of columns.

Each of the next N lines contains M integers describing the city. Every integer is one of 0, 1, and 2.

The last line contains the bomb length K.

Constraints:

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

On the first line, print the number X of bombs you will detonate.

On each of the next X lines, print one bomb position. Print each position as row column, using 1-based row and column numbers.

Every printed bomb must be placed on an empty cell, no printed bomb may have a blast that touches a building, and every 0 cell must be included in the blast range of at least one printed bomb.