Just another board game

"So now I move the piece to $(179,231)$. It's the $999999999$th move of this game. Finally, one move to go!"
"What? Isn't it only the $999999997$th move of this game?"
"Oh, f**k."

After 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's 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's more, there's 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:

• Move the chess piece. If it's Roundgod's turn, he can move the chess piece to any position in the same row(It's also OK to move it to the current position, i.e., not moving it at all). If it's kimoyami's turn, he can move the chess piece to any position in the same column. (It's also OK to move it to the current position, i.e., not moving it at all)


• Screw it. I'm going home. Finish the game immediately.

The 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' 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. Now, Roundgod wants to maximize this value, while kimoyami wants to minimize this value. They don't 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?

The first line contains a number $T(1\leq T\leq 25)$, denoting the number of test cases.

The 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.

Then $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.

It is guaranteed that $\sum (n\times m) \leq 10^6$ over all test cases.

For each test case, output one integer in a line, denoting the final value of the game if both players choose the optimal strategy.

3
2 2 2
1 2
2 1
2 2 1
1 2
2 1
2 3 2
1 3 2
3 2 1

1
2
2

2021“MINIEYE杯”中国大学生算法设计超级联赛（9）