#496. 理想的正方形

理想的正方形

题目描述

原题来自:HAOI 2007

有一个 a×b\red{a\times b} 的整数组成的矩阵,现请你从中找出一个n×n\red{ n\times n }的正方形区域,使得该区域所有数中的最大值和最小值的差最小。

输入格式

第一行为三个整数,分别表示 a,b,n\red{a,b,n} 的值;

第二行至第 a+1\red{a+1} 行每行为 b\red{b }个非负整数,表示矩阵中相应位置上的数。

输出格式

输出仅一个整数,为 a×b\red{a\times b} 矩阵中所有「n×n\red{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

提示

对于 20%\red{20\%} 的数据 2a,b100,n10\red{2\le a,b\le 100,n\le 10}

对于 100%\red{100\% }的数据 2a,b1000,na,nb,n100\red{2\le a,b\le 1000,n\le a,n\le b,n\le 100},矩阵中的所有数都不超过 109\red{10^9}