题目描述

给定一个 $a \times b$ 的非负整数矩阵，你需要在其中找到一个 $n \times n$ 的正方形子矩阵，使得该子矩阵中最大值与最小值的差（极差）最小。输出这个最小的极差。

输入格式

第一行包含三个整数 $a, b, n$。

接下来 $a$ 行，每行 $b$ 个非负整数，表示矩阵。同行相邻整数之间用一个空格分隔。

输出格式

输出一个整数，表示所有 $n \times n$ 正方形子矩阵中极差的最小值。

样例

5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2

1

提示

矩阵中的所有数都是不超过 $10^9$ 的非负整数。

$2 \le a, b \le 1000$，$n \le \min(a, b)$，$n \le 100$。