{"raw_statement":[{"iden":"statement","content":"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.\n\nYour 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?\n\nThe first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.\n\nThe 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.\n\nThen n lines follow, each line contains m integers, giving the grid. All values in the grid are between 1 and 109 (inclusive).\n\nFor each test case, print a single line containing the minimum difference between the largest and smallest beauties after dividing the matrix into 4 parts.\n\n"},{"iden":"input","content":"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 109 (inclusive)."},{"iden":"output","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k, m_k \\in \\mathbb{Z} $ denote the dimensions of the grid, with $ 3 \\leq n_k, m_k \\leq 500 $.  \n- Let $ G_k = (g_{i,j}^{(k)})_{1 \\leq i \\leq n_k,\\ 1 \\leq j \\leq m_k} $ be the grid, where $ g_{i,j}^{(k)} \\in \\mathbb{Z} $ and $ 1 \\leq g_{i,j}^{(k)} \\leq 10^9 $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 100 $  \n2. For each $ k $:  \n   - $ 3 \\leq n_k, m_k \\leq 500 $  \n   - $ 1 \\leq g_{i,j}^{(k)} \\leq 10^9 $ for all $ i,j $  \n\n**Objective**  \nFor each test case $ k $, choose integers $ x \\in \\{2, \\dots, n_k-1\\} $, $ y \\in \\{2, \\dots, m_k-1\\} $ to delete row $ x $ and column $ y $, partitioning the grid into four non-overlapping subgrids:  \n- Top-left: $ \\{(i,j) \\mid 1 \\leq i < x,\\ 1 \\leq j < y\\} $  \n- Top-right: $ \\{(i,j) \\mid 1 \\leq i < x,\\ y < j \\leq m_k\\} $  \n- Bottom-left: $ \\{(i,j) \\mid x < i \\leq n_k,\\ 1 \\leq j < y\\} $  \n- Bottom-right: $ \\{(i,j) \\mid x < i \\leq n_k,\\ y < j \\leq m_k\\} $  \n\nLet $ B_1, B_2, B_3, B_4 $ be the *beauties* (i.e., maximum values) of these four regions respectively.  \nDefine $ D(x,y) = \\max(B_1, B_2, B_3, B_4) - \\min(B_1, B_2, B_3, B_4) $.  \n\nFind:  \n$$\n\\min_{\\substack{2 \\leq x \\leq n_k-1 \\\\ 2 \\leq y \\leq m_k-1}} D(x,y)\n$$","simple_statement":"You are given an n×m grid. You must remove one row (not first or last) and one column (not first or last), splitting the grid into 4 parts. For each part, find the maximum value. Your goal is to minimize the difference between the largest and smallest of these four maximums. Output the smallest possible difference.","has_page_source":false}