Optimal Placement of Distribution Centers

You are given an n×n grid representing a city. Each cell in the grid is either a road (denoted by 0) or a building (denoted by 1). Your task is to choose k road cells in which to place distribution centers such that the maximum Manhattan distance from any cell in the grid to the nearest distribution center is minimized.

The Manhattan distance between two cells with coordinates \( (x_1, y_1) \) and \( (x_2, y_2) \) is defined as:

[ d((x_1,y_1),(x_2,y_2)) = |x_1 - x_2| + |y_1 - y_2| ]

Note: It is guaranteed that there is at least one road cell in the grid and that there exists at least one valid solution. When printing the answer, use 1-indexed positions.

Example:

Input:
5 3
0 1 0 0 1
0 0 1 1 0
1 0 0 0 1
1 1 0 0 0
0 1 0 0 0
Output:
1 1
3 2
5 3

</p>

inputFormat

The first line of input contains two integers n and k, where n is the size of the grid (the grid is n x n) and k is the number of distribution centers to place.

The next n lines each contain n space-separated integers (each either 0 or 1), representing the grid. A value of 0 indicates a road and 1 indicates a building.

outputFormat

Output exactly k lines. Each line should contain two space-separated integers representing the row and column (1-indexed) of a selected road cell where a distribution center is to be placed. The selected centers should minimize the maximum Manhattan distance from any cell in the grid to its nearest distribution center.

## sample

5 3
0 1 0 0 1
0 0 1 1 0
1 0 0 0 1
1 1 0 0 0
0 1 0 0 0

1 1
3 2
5 3

</p>