Minimum Range Submatrix in a Matrix

Given an a × b matrix composed of integers and an integer n, find an n × n contiguous submatrix such that the difference between the maximum and minimum values in that submatrix is minimized. In other words, if the submatrix is denoted by \(M'\), you need to minimize \[ \text{difference} = \max_{0 \le i, j < n} M'_{i,j} - \min_{0 \le i, j < n} M'_{i,j} \] among all possible \(n \times n\) submatrices of the given matrix.

inputFormat

The first line contains three integers: a, b, and n (with \(1 \le n \le \min(a, b)\)). The following a lines each contain b space separated integers, representing the rows of the matrix.

outputFormat

Output a single integer representing the minimum possible difference between the maximum and minimum values among all \(n \times n\) submatrices.

sample

3 3 2
1 5 3
2 2 0
3 4 6

2