Hình vuông lý tưởng (Ideal Square)

Nguồn: Luogu

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho ma trận $a \times b$ số nguyên không âm. Trong mọi hình vuông con kích thước $n \times n$, hãy tìm giá trị nhỏ nhất của hiệu giữa phần tử lớn nhất và nhỏ nhất.

Input

Dòng đầu chứa $a,b,n$. Tiếp theo là $a$ dòng, mỗi dòng có $b$ số nguyên.

Output

In giá trị nhỏ nhất của $\max-\min$ trên mọi hình vuông $n\times n$.

Subtask

• Subtask 1 (20%): $2 \le a,b \le 100$, $n \le 10$.
• Subtask 2 (30%): $2 \le a,b \le 400$, $n \le 50$.
• Subtask 3 (50%): $2 \le a,b \le 1000$, $n \le 100$.

Toàn bộ dữ liệu tuân theo: $2 \le a,b \le 1000$, $n \le a,b$, $n \le 100$, mọi phần tử không vượt $10^9$.

Ví dụ

Input

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

Giải thích

Trong các hình vuông $2\times2$, tồn tại một hình có hiệu lớn nhất trừ nhỏ nhất bằng $1$, và không thể đạt $0$.