{"problem":{"name":"G. Minimax","description":{"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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10197G"},"statements":[{"statement_type":"Markdown","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## Input\n\nThe 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).\n\n## Output\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[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10197G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}