题目描述

縦 $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\lt\ i\leq\ k+h,l\lt\ j\leq\ l+w$ を満たす $(i,j)$ を塗りつぶしたとき、塗りつぶされていないマスに書かれている数が何種類あるか求めよ。

ただし、問題を解く際に実際にマスを塗りつぶすことはない（各問題が独立である）ことに注意してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$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}$

输出格式

$(k,l)$ に対する答えを $\operatorname{ans}_{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}$

题目大意

【题目翻译】

给定一个 $n$ 行 $m$ 列的矩阵，保证所有 $1 \le a_{i, j} \le k$。同时你有一块板子。

每次可以用板子遮住一个 $h$ 行 $w$ 列的子矩阵。求出所有情况下，你一共能看到多少个不同的数。

translated by

【输入格式】

第一行三个数 $n, m, k$。

接下来 $n$ 行，每行 $m$ 个数字，描述这个矩阵。

【输入格式】

共 $n - h + 1$ 行，每行 $m - w + 1$ 个数，第 $i$ 行 $j$ 列的数表示：板子的左上角为 $(i, j)$ 时，答案为多少。

【数据范围】

$1 \le n, m, k \le 300$

保证 $1 \le h \le n$，$1 \le w \le m$。

【样例解释】

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

4 4 3
5 3 4

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

8 8 7
8 9 7
8 9 8

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

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

提示

制約

• $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) $
• 入力される値はすべて整数

Sample Explanation 1

与えられた盤面は下の図のようになります。  例えば、$(k,l)=(0,0)$ のときは塗りつぶされていないマスに書かれている数は $1,3,4,5$ の $4$ 種類なので、$4$ が答えになります。