Salt and Pepper (Large)

Time limit1sMemory limit512 MB

Summary

For each W by W window in the matrix, output the median of its W^2 pixel values.

Level: Medium6 of 10
Topics: Sliding window, Sorting, Matrix
Solved: No attempts yet

Problem

Alice took a photo of the cream cheese spaghetti served for dinner. The salt and pepper scattered over the pasta bothered her, so she asked Bob to erase those specks. Bob pulled a sheet of paper and a pen out of his bag and wrote the problem down like this.

An $M \times N$ matrix $A$ representing the photo is given as input. Each element of the matrix is the brightness of one pixel, where $0$ is the darkest value and $K$ is the brightest value.
An integer $W$ is given as well. Matrix $B$ is defined from $W$ as follows.

$B[i][j] = \mathrm{median}(A[i+x][j+y]), \quad 1 \le i \le M-W+1, \; 1 \le j \le N-W+1, \; 0 \le x, y < W$

Here $A[i+x][j+y]$ is the element in row $i+x$ , column $j+y$ of matrix $A$ . In other words, $B[i][j]$ is the median of the $W^2$ values inside the $W \times W$ square whose top left corner is row $i$ , column $j$ of $A$ .

Compute matrix $B$ from the given matrix $A$ and integer $W$ .

Figure: how matrix $B$ is built from matrix $A$ and $W$ .

Bob opened his laptop and started writing the program, but it did not go well, and the spaghetti began to go soggy. Write the program for Bob before the spaghetti is ruined.

The median is the value that sits in the middle once the given values are sorted by size. Among the five values 1, 2, 3, 3, 100 the one in the middle is 3, so the median is 3. $W$ is odd, so $W^2$ is odd too and the median is always a single value.

Input

The first line contains the matrix size $M$ and $N$ ( $1 \le M, N \le 300$ ), the maximum brightness $K$ ( $1 \le K \le 100{,}000$ ), and the integer $W$ ( $1 \le W \le \min(M, N)$ ), separated by spaces in that order. $W$ is odd.

Each of the next $M$ lines contains $N$ integers. The $j$ -th integer on line $1+i$ is the element in row $i$ , column $j$ of matrix $A$ , and it is between $0$ and $K$ .

Output

Print matrix $B$ over $M-W+1$ lines. Each line holds $N-W+1$ integers separated by one space.

Hint

If $W$ is $1$ , every square holds a single value, so $B$ equals $A$ .

Suppose $W$ is $3$ and a square holds 5, 1, 2, 12, 10, 3, 8, 12, 19. Sorted, the values are 1, 2, 3, 5, 8, 10, 12, 12, 19, and the fifth value is in the middle, so the median is 8.

Examples3

Example 1

Input

Expected output

1 2 3
4 5 6
7 8 9

Example 2
Input
```
3 3 10 3
1 2 3
4 5 6
7 8 9
```
Expected output
```
5
```

Example 3

Input

5 5 20 3
5 1 2 8 10
12 10 3 20 7
8 12 19 18 15
17 19 2 5 13
11 2 4 14 16

Expected output

8 10 10
12 12 13
11 12 14