Description

Given an $a \times b$ matrix of integers, find an $n \times n$ square region such that the difference between the maximum and minimum numbers in that region is minimized.

Input Format

The first line contains 3 integers, representing the values of $a$, $b$, and $n$.

From the second line to the $(a+1)$-th line, each line contains $b$ nonnegative integers, representing the numbers at the corresponding positions in the matrix. Adjacent numbers on the same line are separated by a single space.

Output Format

Output a single integer: the minimal possible difference between the maximum and the minimum among all $n \times n$ square regions in the $a \times b$ matrix.

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

1

Hint

All numbers in the matrix do not exceed 1,000,000,000.

Constraints:

For 20% of the testdata, $2 \le a, b \le 100$, $n \le a$, $n \le b$, $n \le 10$.

For 100% of the testdata, $2 \le a, b \le 1000$, $n \le a$, $n \le b$, $n \le 100$.

Translated by ChatGPT 5