Description

Original source: HAOI 2007

There is a matrix of integers with dimensions $a\times b$. Your task is to find an $n\times n$ square submatrix within it such that the difference between the maximum and minimum values in this submatrix is minimized.

Input Format

The first line contains three integers: $a$, $b$, and $n$;

The next $a$ lines each contain $b$ non-negative integers, representing the numbers in the corresponding positions of the matrix.

Output Format

Output a single integer, which is the minimum difference between the maximum and minimum values among all possible $n\times n$ square submatrices in the $a\times b$ matrix.

Sample 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

Data Range and Hints

For $20\%$ of the data, $2\le a,b\le 100$ and $n\le 10$;
For $100\%$ of the data, $2\le a,b\le 1000$, $n\le a$, $n\le b$, $n\le 100$, and all numbers in the matrix do not exceed $10^9$.