Salt and Pepper (Small)

Gap and Eul are a couple. One evening they went to a restaurant for cream cheese spaghetti. The plate looked good, so Gap took a photo with a phone, and while getting ready to post it on social media Gap noticed the salt and pepper scattered over the spaghetti.

Gap did not like the salt and pepper in the photo and asked Eul to remove them. Eul answered that this was easy, pulled paper and a pen out of a bag, and wrote the problem down like this.

• An $M \times N$ matrix $A$ describing the photo is given as input. Each entry is the brightness of one pixel, where 0 is the darkest and $K$ is the brightest.
• An integer $W$ is also given as input. It defines a matrix $B$ as follows.
  • $B[i][j] = \mathrm{median}(A[i+x][j+y])$
  • where $1 \le i \le M-W+1$, $1 \le j \le N-W+1$, $0 \le x, y < W$.
  • $A[i+x][j+y]$ is the entry in row $i+x$ and column $j+y$ of matrix $A$, and median is the middle value.
• Compute matrix $B$ from matrix $A$ and the integer $W$.

How matrix $B$ is built from matrix $A$ and $W$

Eul opened a laptop and started writing the program, but it did not go well and the spaghetti began to go soft. Write the program for Eul before the spaghetti is ruined.

The median of a set of values is the value that sits in the middle once they are sorted by size. For 1, 2, 3, 3, 100 the median is 3, because 3 is in the middle. $W$ is odd, so the number of values in one window, $W^2$, is odd as well and the median is always a single value.

The first line contains the matrix size $M$ and $N$ ($1 \le M, N \le 30$), the maximum brightness $K$ ($1 \le K \le 10\,000$), and the integer $W$ ($1 \le W \le \min(M, N)$), separated by spaces. $W$ is odd.

Each of the next $M$ lines contains $N$ integers between 0 and $K$. The $j$th integer on the $i$th of these lines is the entry in row $i$ and column $j$ of matrix $A$.

Print matrix $B$ on $M-W+1$ lines. Each line holds $N-W+1$ integers separated by a single space.