Problem Description

Given \( n, m, r, s \) and an \( n \times m \) integer matrix \( A \), find the maximum element of each \( r \times s \) submatrix.

Problem Description

While wandering around Building 21, you came across a wall completely covered with numbers, arranged in a table of \( n \) rows and \( m \) columns. Soon you noticed that there was a frame leaning against the wall large enough to frame \( r \) rows and \( s \) columns of the table on the wall. And next to the frame you found a pencil and a piece of paper containing an empty table.

You are sad that the table on the piece of paper is empty, so you decided to play around with the frame to fill it.

You leaned the frame against the wall so that the number in the \( i \)-th row and \( j \)-th column is in the upper left corner, and the borders of the frame are parallel to the edges of the wall. Considering the numbers inside the frame, and since you like large numbers, you have decided to write the largest among them in the \( i \)-th row and \( j \)-th column of the table on the piece of paper.

You repeated the process for every possible position of the frame on the wall (such that the frame is entirely on the wall, and that there are exactly \( r \times s \) numbers inside it), making sure that the edges of the frame are parallel to the edges of the wall.

When you were done, the table on the piece of paper was even more beautiful than the one on the wall. What numbers are in the table on the piece of paper?

Problem Summary

Given \( n, m, r, s \) and an \( n \times m \) integer matrix \( A \), find the maximum element of each \( r \times s \) submatrix.

Input Format

The first line contains two integers \( n \) and \( m \) representing the height and width of the matrix.

The next \( n \) lines each contain \( m \) integers, representing the matrix \( A \).

The last line contains two integers \( r \) and \( s \).

Output Format

Output \( n - r + 1 \) lines, each containing \( m - s + 1 \) numbers. The number at the \( i \)-th row and \( j \)-th column represents the maximum element of the \( r \times s \) submatrix with the top-left corner at \( (i, j) \), i.e., \( \max\limits_{i \leq x \leq i + r - 1, j \leq y \leq j + s - 1} A_{x, y} \).

Sample Input and Output

Sample Input #1

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

Sample Output #1

4

Sample Input #2

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

Sample Output #2

2 3 4
4 3 4

Sample Input #3

5 5
-1 -3 -4 -2 4
-8 -7 -9 -10 11
5 2 -8 -2 1
13 -3 -2 -6 -9
11 6 2 7 4
2 3

Sample Output #3

-1 -2 11
5 2 11
13 2 1
13 7 7

Notes

Sample Explanation #1

There is only one \( 3 \times 3 \) submatrix, which is the entire matrix, and its maximum element is \( 4 \).

Sample Explanation #2

The matrix and its each \( 2 \times 1 \) submatrix are shown below, with the maximum values highlighted in red:

Data Range

For \( 100\% \) of the data, \( 1 \leq n, m \leq 4000 \), \( \lvert A_{i, j} \rvert \leq 10000 \), \( 1 \leq r \leq n \), \( 1 \leq s \leq m \).

This problem is group testing.

Notes

This problem's score is set according to the original COCI contest, with a full score of 110.

The problem is translated from COCI2022-2023 CONTEST #1 T3 AN2DL.

见题面 Input 部分

见题面 Output 部分