405481: GYM101972 G Minimax

You are given a grid consisting of n rows each of which is dived into m columns. The rows are numbered from 1 to n from top to bottom, and the columns are numbered from 1 to m from left to right. Each cell is identified by a pair (x, y), which means that the cell is located in the row x and column y.

Your goal is to delete a row x (1 < x < n) and a column y (1 < y < m), after this the matrix will be divided into 4 parts. Let us define the beauty of each part as the maximum value inside it. Your task is to choose x and y such that the difference between the largest and smallest beauties is as minimal as possible. Can you?

The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.

The first line of each test case contains two integers n and m (3 ≤ n, m ≤ 500), specifying the grid size, in which n is the number of rows and m is the number of columns.

Then n lines follow, each line contains m integers, giving the grid. All values in the grid are between 1 and 10⁹ (inclusive).

For each test case, print a single line containing the minimum difference between the largest and smallest beauties after dividing the matrix into 4 parts.

2
3 3
9 5 8
3 4 1
6 2 7
4 4
22 7 3 11
3 1 8 9
5 2 4 3
13 5 6 9

3
13