{"raw_statement":[{"iden":"statement","content":"You are given a grid $g$ consisting of $n$ rows each of which is divided into $m$ columns. The grid contains unique values between $1$ and $n times m$ (inclusive).\n\nAlso, you are given two values $h$ and $w$, and your task is to find the smallest median value that can be found in a rectangle of size $h times w$.\n\nA rectangle of size $h times w$ is a rectangle consisting of $h$ rows and $w$ columns such that its top left corner is at a cell ($a, thin b$) and its right bottom corner is at a cell ($c, thin d$), and the following conditions are satisfied: ($c -a + 1 equiv h$) and ($d -b + 1 equiv w$).\n\nThe median of a set of numbers is the middle element in the sorted list of the given set. For example, the median of ${2, 1, 3}$ is $2$ and the median of ${4, 2, 3, 1, 5}$ is $3$.\n\nThe first line contains four integers $n$, $m$, $h$, and $w$ ($1 <= n, thin m <= 10^3$, $1 <= h, thin w <= n$), in which $n$ and $m$ are the number of rows and columns in the grid, respectively, and $h$ and $w$ are representing the size of the required rectangle. Both $h$ and $w$ are odd integers.\n\nThen $n$ lines follow, each line contains $n$ integers, giving the grid. It is guaranteed that the grid contains unique values between $1$ and $n times m$ (inclusive).\n\nPrint a single line containing the smallest median value that can be found in a rectangle of size $h times w$.\n\nIn the first test case, there are $4$ possible rectangles of size $3 times 3$, which are: \n\nSo, the smallest median value that can be found in a rectangle of size $3 times 3$ is $6$.\n\n"},{"iden":"input","content":"The first line contains four integers $n$, $m$, $h$, and $w$ ($1 <= n, thin m <= 10^3$, $1 <= h, thin w <= n$), in which $n$ and $m$ are the number of rows and columns in the grid, respectively, and $h$ and $w$ are representing the size of the required rectangle. Both $h$ and $w$ are odd integers.Then $n$ lines follow, each line contains $n$ integers, giving the grid. It is guaranteed that the grid contains unique values between $1$ and $n times m$ (inclusive)."},{"iden":"output","content":"Print a single line containing the smallest median value that can be found in a rectangle of size $h times w$."},{"iden":"note","content":"In the first test case, there are $4$ possible rectangles of size $3 times 3$, which are:   Starts at ($1, thin 1$). $arrow.r$ Contains elements: ${13, 16, 15, 5, 2, 8, 14, 11, 12}$. $arrow.r$ Median value = $12$.  Starts at ($1, thin 2$). $arrow.r$ Contains elements: ${16, 15, 4, 2, 8, 9, 11, 12, 10}$. $arrow.r$ Median value = $10$.  Starts at ($2, thin 1$). $arrow.r$ Contains elements: ${5, 2, 8, 14, 11, 12, 1, 6, 3}$. $arrow.r$ Median value = $6$.  Starts at ($2, thin 2$). $arrow.r$ Contains elements: ${2, 8, 9, 11, 12, 10, 6, 3, 7}$. $arrow.r$ Median value = $8$. So, the smallest median value that can be found in a rectangle of size $3 times 3$ is $6$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m, h, w \\in \\mathbb{Z}^+ $ with $ h, w $ odd, $ 1 \\leq h \\leq n \\leq 10^3 $, $ 1 \\leq w \\leq m \\leq 10^3 $.  \nLet $ G \\in \\mathbb{Z}^{n \\times m} $ be a grid with distinct entries from $ \\{1, 2, \\dots, nm\\} $.  \n\nA valid $ h \\times w $ rectangle is defined by its top-left corner $ (a, b) $, where $ 1 \\leq a \\leq n - h + 1 $, $ 1 \\leq b \\leq m - w + 1 $, and spans rows $ a $ to $ a + h - 1 $ and columns $ b $ to $ b + w - 1 $.  \n\nLet $ R_{a,b} \\subseteq \\mathbb{Z} $ denote the multiset of values in the rectangle starting at $ (a, b) $, with $ |R_{a,b}| = h \\cdot w $.  \n\nThe median of a finite set of size $ h \\cdot w $ (odd) is the $ \\left( \\frac{h \\cdot w + 1}{2} \\right) $-th smallest element in the sorted version of the set.  \n\n**Constraints**  \n1. $ G $ contains exactly $ nm $ distinct integers from $ 1 $ to $ nm $.  \n2. $ h $ and $ w $ are odd.  \n\n**Objective**  \nFind  \n$$\n\\min_{\\substack{1 \\leq a \\leq n - h + 1 \\\\ 1 \\leq b \\leq m - w + 1}} \\left( \\text{median}(R_{a,b}) \\right)\n$$","simple_statement":"You are given an n×m grid with unique numbers from 1 to n×m.  \nYou must find a h×w rectangle (h and w are odd) inside the grid.  \nThe median of the h×w numbers in the rectangle is the middle number when sorted.  \nFind the smallest possible median among all such rectangles.","has_page_source":false}