Problem 3808 --Just another board game

3808: Just another board game

上一题 正确率: $0.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $128$ 兆字节/Megabyte(s)
提交总数 $0$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

"So now I move the piece to (179,231). It's the 999999999th move of this game. Finally, one move to go!"
"What? Isn't it only the 999999997th 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 ith row and jth column equal to aij. 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?

Input

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

The first line of each test case contains three integers n,m,k(n,m≥1,1≤n×m≤105,1≤k≤1018), denoting the size of the chessboard and the maximum number of turns the game will last, respectively.

Then n lines follow, the ith(1≤i≤n) of the n lines contain m integers ai1,ai2,…,aim, where aij(0≤aij≤109) denotes the he number written on the grid on the ith row and jth column.

It is guaranteed that ∑(n×m)≤106 over all test cases.

Output

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

Sample Input复制

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

Sample Output复制

1
2
2

推荐代码 查看3808 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战

赛题来源/所属竞赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛