Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3335
Filtering

Time Limit: 3 Seconds      Memory Limit: 32768 KB

Median filtering is a common method in image processing. It is particularly useful to reduce speckle noise and pepper noise. Its edge-preserving nature makes it useful in cases where edge blurring is undesirable.

Median filtering is defined as follow. Let X be the matrix represents an image, and the matrix's size is p * q. The coordinate of the matrix's top left element is (1, 1). The result of the median filtering with an m * n (where m, n are both odd integers) rectangle window is also a matrix Y. The window scan the image from left to right and from top to bottom. We defined the new matrix as follow:

For each (i, j) where 1 <= i <= n and 1 <= j <= m,

  • when (m + 1) / 2 <= i <= p - (m - 1) / 2 and (n + 1) / 2 <= j <= q - (n - 1) / 2, consider the windows whose center is at (i, j)). Y(i, j) = the median number (rank the middle) among the numbers that the window covers.

  • In other cases, Y(i, j) = X(i, j)

For example, if the window's size is 3 * 3 and the matrix X is:

1 2 3 3 2
1 4 2 3 3
2 5 6 2 3
3 2 1 4 2
3 3 2 7 1
4 5 6 7 8
1 1 2 3 4

then the new matrix Y will be:

1 2 3 3 2
1 2 3 3 3
2 2 3 3 3
3 3 3 2 2
3 3 4 4 1
4 3 3 4 8
1 1 2 3 4

Now you are given the matrix X, and your task is to calculate the matrix Y.

Input

There are multicases.

In the first line, there are two numbers p and q (1 <= p, q <= 500), which indicate the size of matrix X. Follow p lines, and each line has q integers, which are all in range [0, 255].

There are two integers m, n (1 <= m, n <= 49, p >= m, q >= n, and m, n are odd integers. ) in the last line, which indicate the window's size.

There is a line between cases.

Output

You should output the matrix Y. Print a line after each case.

Sample Input

5 5
1 2 3 3 2
1 4 2 3 3
2 5 6 2 3
3 2 1 4 2
3 3 2 7 1
3 3

7 5
1 2 3 3 2
1 4 2 3 3
2 5 6 2 3
3 2 1 4 2
3 3 2 7 1
4 5 6 7 8
1 1 2 3 4
3 3

Sample Output

1 2 3 3 2
1 2 3 3 3
2 2 3 3 3
3 3 3 2 2
3 3 2 7 1

1 2 3 3 2
1 2 3 3 3
2 2 3 3 3
3 3 3 2 2
3 3 4 4 1
4 3 3 4 8
1 1 2 3 4


Author: LIN, Yue
Source: ZOJ Monthly, May 2010
Submit    Status