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?
Input

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^9 (inclusive).
Output

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.
Example
Input

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

Output

3
13

题意：给你n行m列的矩阵，你可以删去非边缘的一行一列，将矩阵分成四个部分，每个部分所有数的最大数为这一部分的val，再定义差值为四个部分中val最大的部分减val最小的部分为差值，问你删去一行一列之后最小的差值是到多少。

题解：预处理一下4个方向,再枚举每种分割

<mark>注意：数组初始化(╥╯^╰╥)</mark>

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int mp[505][505],dp1[505][505],dp2[505][505],dp3[505][505],dp4[505][505];
int main(){
	int T,n,m;
	scanf("%d",&T);
	while(T--){
		memset(dp1,0,sizeof(dp1));
		memset(dp2,0,sizeof(dp2));
		memset(dp3,0,sizeof(dp3));
		memset(dp4,0,sizeof(dp4)); 
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				scanf("%d",&mp[i][j]);
			}
		}
		//左上角 
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				dp1[i][j]=max(mp[i][j],max(dp1[i-1][j],dp1[i][j-1]));
			}
		}
		//右上角 
		for(int i=1;i<=n;i++){
			for(int j=m;j>=1;j--){
				dp2[i][j]=max(mp[i][j],max(dp2[i-1][j],dp2[i][j+1])); 
			}
		} 
		//左下角
		for(int i=n;i>=1;i--){
			for(int j=1;j<=m;j++){
				dp3[i][j]=max(mp[i][j],max(dp3[i+1][j],dp3[i][j-1]));
			}
		} 
		//右下角
		for(int i=n;i>=1;i--){
			for(int j=m;j>=1;j--){
				dp4[i][j]=max(mp[i][j],max(dp4[i+1][j],dp4[i][j+1]));
			}
		} 
		int ans=999999999;
		//枚举分割点 
		for(int i=2;i<n;i++){
			for(int j=2;j<m;j++){
				int maxx=max(max(dp1[i-1][j-1],dp2[i-1][j+1]),max(dp3[i+1][j-1],dp4[i+1][j+1]));
				int minn=min(min(dp1[i-1][j-1],dp2[i-1][j+1]),min(dp3[i+1][j-1],dp4[i+1][j+1]));
				ans=min(maxx-minn,ans);
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}