{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\u003ci\u003e\"So now I move the piece to $(179,231)$. It\u0027s the $999999999$th move of this game. Finally, one move to go!\"\u003c/i\u003e\u003cbr\u003e\u003ci\u003e\"What? Isn\u0027t it only the $999999997$th move of this game?\"\u003c/i\u003e\u003cbr\u003e\u003ci\u003e\"Oh, f**k.\"\u003c/i\u003e\u003cbr\u003e\u003cbr\u003eAfter playing some games of Go, Roundgod and kimoyami decide to try something different. Now they are playing a new kind of game on a chessboard. The chessboard is a grid board with $n$ rows and $m$ columns. We assume that the upper left corner of the chessboard has coordinate $(1,1)$, and the lower right corner of the chessboard has coordinate $(n,m)$. There\u0027s a number on every grid of the board, with the number written on the grid on the $i$th row and $j$th column equal to $a_{ij}$. What\u0027s more, there\u0027s a chess piece on the upper left corner(i.e., $(1,1)$) of the chessboard initially. Now the two players take turns to choose one of the following operations, starting from Roundgod:\u003cbr\u003e\u003cul\u003e\u003cli\u003eMove the chess piece. If it\u0027s Roundgod\u0027s turn, he can move the chess piece to any position in the \u003cb\u003esame row\u003c/b\u003e(It\u0027s also OK to move it to the current position, i.e., not moving it at all). If it\u0027s kimoyami\u0027s turn, he can move the chess piece to any position in the \u003cb\u003esame column\u003c/b\u003e. (It\u0027s also OK to move it to the current position, i.e., not moving it at all)\u003c/li\u003e\u003cbr\u003e \u003cli\u003e \u003ci\u003eScrew it. I\u0027m going home.\u003c/i\u003e Finish the game immediately.\u003c/li\u003e\u003c/ul\u003e \u003cbr\u003eThe game ends when either of the two players chooses the second operation or when the game has already been going on for $k$ turns. (Either of the two players\u0027 operations counts as one turn). The value of the game is defined as the number on the grid where the chess piece lands when the game ends. \u003cb\u003eNow, Roundgod wants to maximize this value, while kimoyami wants to minimize this value.\u003c/b\u003e They don\u0027t have the patience to actually play this game for possibly that many turns, so they want you to calculate what will be the final value of the game if both players choose the optimal strategy?\u003cbr\u003e\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains a number $T(1\\leq T\\leq 25)$, denoting the number of test cases.\u003cbr\u003e\u003cbr\u003eThe first line of each test case contains three integers $n,m,k(n,m\\geq 1,1\\leq n\\times m\\leq 10^5,1\\leq k\\leq 10^{18})$, denoting the size of the chessboard and the maximum number of turns the game will last, respectively.\u003cbr\u003e\u003cbr\u003eThen $n$ lines follow, the $i$th$(1\\leq i\\leq n$) of the $n$ lines contain $m$ integers $a_{i1},a_{i2},\\dots,a_{im}$, where $a_{ij}(0\\leq a_{ij}\\leq 10^9)$ denotes the he number written on the grid on the $i$th row and $j$th column.\u003cbr\u003e\u003cbr\u003eIt is guaranteed that $\\sum (n\\times m) \\leq 10^6$ over all test cases."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output one integer in a line, denoting the final value of the game if both players choose the optimal strategy."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n2 2 2\r\n1 2\r\n2 1\r\n2 2 1\r\n1 2\r\n2 1\r\n2 3 2\r\n1 3 2\r\n3 2 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n2\r\n2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}