102784: [AtCoder]ABC278 E - Grid Filling

Problem Statement

You have a grid with $H$ rows from top to bottom and $W$ columns from left to right. We denote by $(i, j)$ the square at the $i$-th row from the top and $j$-th column from the left. $(i,j)\ (1\leq i\leq H,1\leq j\leq W)$ has an integer $A _ {i,j}$ between $1$ and $N$ written on it.

You are given integers $h$ and $w$. For all pairs $(k,l)$ such that $0\leq k\leq H-h$ and $0\leq l\leq W-w$, solve the following problem:

• If you black out the squares $(i,j)$ such that $k\lt i\leq k+h$ and $l\lt j\leq l+w$, how many distinct integers are written on the squares that are not blacked out?

Note, however, that you do not actually black out the squares (that is, the problems are independent).

Constraints

• $1 \leq H,W,N \leq 300$
• $1 \leq h \leq H$
• $1 \leq w \leq W$
• $(h,w)\neq(H,W)$
• $1 \leq A _ {i,j} \leq N\ (1\leq i\leq H,1\leq j\leq W)$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$H$ $W$ $N$ $h$ $w$
$A _ {1,1}$ $A _ {1,2}$ $\dots$ $A _ {1,W}$
$A _ {2,1}$ $A _ {2,2}$ $\dots$ $A _ {2,W}$
$\vdots$
$A _ {H,1}$ $A _ {H,2}$ $\dots$ $A _ {H,W}$

Output

Print the answers in the following format, where $\operatorname{ans}_{k,l}$ denotes the answer to $(k, l)$:

$\operatorname{ans} _ {0,0}$ $\operatorname{ans} _ {0,1}$ $\dots$ $\operatorname{ans} _ {0,W-w}$
$\operatorname{ans} _ {1,0}$ $\operatorname{ans} _ {1,1}$ $\dots$ $\operatorname{ans} _ {1,W-w}$
$\vdots$
$\operatorname{ans} _ {H-h,0}$ $\operatorname{ans} _ {H-h,1}$ $\dots$ $\operatorname{ans} _ {H-h,W-w}$

Sample Input 1

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

Sample Output 1

4 4 3
5 3 4

The given grid is as follows:

For example, when $(k,l)=(0,0)$, four distinct integers $1,3,4$, and $5$ are written on the squares that are not blacked out, so $4$ is the answer.

Sample Input 2

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

Sample Output 2

8 8 7
8 9 7
8 9 8

Sample Input 3

9 12 30 4 7
2 2 2 2 2 2 2 2 2 2 2 2
2 2 20 20 2 2 5 9 10 9 9 23
2 29 29 29 29 29 28 28 26 26 26 15
2 29 29 29 29 29 25 25 26 26 26 15
2 29 29 29 29 29 25 25 8 25 15 15
2 18 18 18 18 1 27 27 25 25 16 16
2 19 22 1 1 1 7 3 7 7 7 7
2 19 22 22 6 6 21 21 21 7 7 7
2 19 22 22 22 22 21 21 21 24 24 24

Sample Output 3

21 20 19 20 18 17
20 19 18 19 17 15
21 19 20 19 18 16
21 19 19 18 19 18
20 18 18 18 19 18
18 16 17 18 19 17

问题描述

你有一个从上到下有$H$行、从左到右有$W$列的网格。我们用$(i, j)$表示从上数第$i$行、从左数第$j$列的格子。$(i,j)\ (1\leq i\leq H,1\leq j\leq W)$上写着一个在$1$到$N$之间的整数$A _ {i,j}$。

给你两个整数$h$和$w$。对于所有满足$0\leq k\leq H-h$和$0\leq l\leq W-w$的$(k,l)$，解决以下问题：

• 如果你把从第$k+1$行到第$k+h$行、从第$l+1$列到第$l+w$列的格子涂黑，那么在没有被涂黑的格子上，有多少个不同的整数被写在上面？

但是请注意，你实际上并没有真的涂黑格子（即，问题之间是独立的）。

约束

• $1 \leq H,W,N \leq 300$
• $1 \leq h \leq H$
• $1 \leq w \leq W$
• $(h,w)\neq(H,W)$
• $1 \leq A _ {i,j} \leq N\ (1\leq i\leq H,1\leq j\leq W)$
• 输入中的所有值都是整数。

输入

输入通过标准输入以以下格式给出：

$H$ $W$ $N$ $h$ $w$
$A _ {1,1}$ $A _ {1,2}$ $\dots$ $A _ {1,W}$
$A _ {2,1}$ $A _ {2,2}$ $\dots$ $A _ {2,W}$
$\vdots$
$A _ {H,1}$ $A _ {H,2}$ $\dots$ $A _ {H,W}$

输出

以以下格式打印答案，其中$\operatorname{ans}_{k,l}$表示$(k, l)$的答案：

$\operatorname{ans} _ {0,0}$ $\operatorname{ans} _ {0,1}$ $\dots$ $\operatorname{ans} _ {0,W-w}$
$\operatorname{ans} _ {1,0}$ $\operatorname{ans} _ {1,1}$ $\dots$ $\operatorname{ans} _ {1,W-w}$
$\vdots$
$\operatorname{ans} _ {H-h,0}$ $\operatorname{ans} _ {H-h,1}$ $\dots$ $\operatorname{ans} _ {H-h,W-w}$

样例输入 1

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

样例输出 1

4 4 3
5 3 4

给定的网格如下：

例如，当$(k,l)=(0,0)$时，四个不同的整数$1,3,4$和$5$被写在没有被涂黑的格子上，所以答案是$4$。

样例输入 2

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

样例输出 2

8 8 7
8 9 7
8 9 8

样例输入 3

9 12 30 4 7
2 2 2 2 2 2 2 2 2 2 2 2
2 2 20 20 2 2 5 9 10 9 9 23
2 29 29 29 29 29 28 28 26 26 26 15
2 29 29 29 29 29 25 25 8 25 15 15
2 29 29 29 29 29 25 25 8 25 15 15
2 18 18 18 18 1 27 27 25 25 16 16
2 19 22 1 1 1 7 3 7 7 7 7
2 19 22 22 6 6 21 21 21 7 7 7
2 19 22 22 22 22 21 21 21 24 24 24

样例输出 3

21 20 19 20 18 17
20 19 18 19 17 15
21 19 20 19 18 16
21 19 19 18 19 18
20 18 18 18 19 18
18 16 17 18 19 17