[HAOI2007]理想的正方形

给定一个由整数组成的 $a\times b$ 矩阵，请从中选出一个 $n\times n$ 的正方形区域，使该区域内最大值与最小值之差最小。

输入格式

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

接下来 $a$ 行，每行包含 $b$ 个非负整数。其中 $x_{i,j}$ 表示矩阵第 $i$ 行、第 $j$ 列的整数。每行相邻两个整数之间用一个空格分隔。

输出格式

输出一个整数，表示所有 $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

数据范围

• $2\le a,b\le 1000$；
• $1\le n\le \min(a,b)$；
• $0\le x_{i,j}\le 10^9$。

来源与许可

本题为 HAOI 2007 试题「理想的正方形」，题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

1