You are given an $a \times b$ matrix of integers. Please find an $n \times n$ square region within it such that the difference between the maximum and minimum values in that region is minimized.

Input

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

The next $a$ lines each contain $b$ non-negative integers, representing the numbers at the corresponding positions in the matrix. Adjacent numbers in each line are separated by a space.

Output

A single integer, which is the minimum value of the "difference between the maximum and minimum integers in an $n \times n$ square region" among all such regions in the $a \times b$ matrix.

Examples

Input 1

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

Output 1

1

Constraints

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

(2) For 20% of the data: $2 \le a, b \le 100$, $n \le a$, $n \le b$, $n \le 10$.

(3) For 100% of the data: $2 \le a, b \le 1000$, $n \le a$, $n \le b$, $n \le 100$.