Anya and Becky found an N\times M grid that contains distinct integers, and decided to play a game on it. The integer present at the intersection of the i-th row and j-th column is denoted A_{i, j}.

They place a token at the top-left corner (cell (1, 1)), and then take turns moving the token towards the bottom-right corner (cell (N, M)), each time moving the token one step right or down. Becky moves first.

Suppose the token is at position (i, j). Then,
Becky can choose to move the token to either (i+1, j) or (i, j+1).
Anya, in her infinite ~greed~ wisdom, will always move the token to whichever cell has the larger value. That is,
- She will move the token to cell (i+1, j) if A_{i+1, j} > A_{i, j+1}
- She will move the token to cell (i, j+1) if A_{i+1, j} < A_{i, j+1}

Of course, the token must remain inside the grid at all times, so if i = N they cannot move it down and if j = M they cannot move it right.

Let K be the maximum value the two encounter on their path from (1, 1) to (N, M). Becky would like to rein in Anya a bit, so please help her: if she makes her moves optimally, what is the minimum possible value of K?

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains two space-separated integers N and M — the number of rows and columns of the grid.
- The next N lines describe the grid. The i-th of these N lines contains M space-separated integers A_{i, 1}, A_{i, 2}, \ldots, A_{i, M}.

------ Output Format ------ 

For each test case, output on a new line the minimum possible value of K, if Becky chooses her moves optimally.

------ Constraints ------ 

$1 ≤ T ≤ 3\cdot 10^{4}$
$1 ≤ N, M ≤ 5\cdot 10^{5}$
$1 ≤ N\times M ≤ 5\cdot 10^{5}$
$1 ≤ A_{i, j} ≤ N\cdot M$
- All the $A_{i, j}$ within a single testcase will be distinct.
- The sum of $N\times M$ across all test cases won't exceed $5\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
2 2
4 1
2 3
2 2
1 4
2 3
3 4
4 2 11 10
6 7 1 9
5 12 3 8

----- Sample Output 1 ------ 
4
3
9

----- explanation 1 ------ 
Test case $1$: Since $A_{1, 1} = 4$ is the largest value in the grid, no matter what path is taken the maximum value is going to be $4$.

Test case $2$: Becky can move the token down in the first move, which forces Anya to move right on hers. This gives the path $1 \to 2 \to 3$ with a maximum of $3$, which is the best possible.

Test case $3$: The optimal path is $4 \to 6 \to 7 \to 1 \to 9 \to 8$, with a maximum of $9$.  
Note that if Anya had chosen to move down to $5$ when at $6$, she could have forced the maximum to be $12$. However, $5 < 7$ so she will never choose to do this.

Difficulty: VERY_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
from collections import deque

def playerturnatpoint(a, b):
	if a % 2 == b % 2:
		return 1
	else:
		return 2

def solve(arr, dp, x, y, queue=deque()):
	lenarr = x
	lenarr0 = y
	if x > 0:
		queue.append([x - 1, y])
	if y > 0:
		queue.append([x, y - 1])
	while len(queue) > 0:
		(x, y) = queue.popleft()
		if y == lenarr0 and x > 0:
			queue.append([x - 1, y])
		if y > 0:
			queue.append([x, y - 1])
		turn = playerturnatpoint(x, y)
		if x == lenarr and y != lenarr0:
			dp[x][y] = max(arr[x][y], dp[x][y + 1])
		elif y == lenarr0 and x != lenarr:
			dp[x][y] = max(arr[x][y], dp[x + 1][y])
		elif turn == 2:
			if arr[x][y + 1] > arr[x + 1][y]:
				dp[x][y] = max(arr[x][y], dp[x][y + 1])
			else:
				dp[x][y] = max(arr[x][y], dp[x + 1][y])
		elif turn == 1:
			dp[x][y] = max(arr[x][y], min(dp[x + 1][y], dp[x][y + 1]))
for _ in range(int(input())):
	(N, M) = list(map(int, input().split()))
	arr = []
	for i in range(N):
		arr.append(list(map(int, input().split())))
	dp = [[0] * M for _ in range(N)]
	dp[-1][-1] = arr[-1][-1]
	solve(arr, dp, N - 1, M - 1)
	print(dp[0][0])


from collections import Counter, defaultdict
import sys

def is_valid(mat, u, v):
	if u < len(mat) and v < len(mat[0]):
		return 1
	return 0

def sol(r, c, mat):
	count = 0
	vis = [[0 for _ in range(c)] for _ in range(r)]
	q = [(0, (0, 0))]
	maxArr = [[0 for _ in range(c)] for _ in range(r)]
	for i in range(r):
		for j in range(c):
			maxArr[i][j] = mat[i][j]
	while q:
		curr = q.pop(0)
		x = curr[1][0]
		y = curr[1][1]
		count = curr[0]
		if x >= r or y >= c:
			continue
		X = [1, 0]
		Y = [0, 1]
		vis[x][y] = 1
		if count == 0:
			for i in range(2):
				u = X[i] + x
				v = Y[i] + y
				if is_valid(mat, u, v):
					if vis[u][v]:
						maxArr[u][v] = min(maxArr[u][v], max(mat[u][v], maxArr[x][y]))
					else:
						maxArr[u][v] = max(mat[u][v], maxArr[x][y])
						q.append((1 - count, (u, v)))
						vis[u][v] = 1
		else:
			val = 0
			ind = -1
			if x + 1 < r:
				if mat[x + 1][y] > val:
					val = max(val, mat[x + 1][y])
					ind = 0
			if y + 1 < c:
				if mat[x][1 + y] > val:
					val = max(val, mat[x][1 + y])
					ind = 1
			if ind == 1:
				q.append((1 - count, (x, y + 1)))
				if vis[x][y + 1] == 1:
					maxArr[x][y + 1] = min(maxArr[x][y + 1], max(maxArr[x][y], mat[x][y + 1]))
				else:
					maxArr[x][y + 1] = max(maxArr[x][y], mat[x][y + 1])
				vis[x][y + 1] = 1
			if ind == 0:
				q.append((1 - count, (x + 1, y)))
				if vis[x + 1][y] == 1:
					maxArr[x + 1][y] = min(maxArr[x + 1][y], max(maxArr[x][y], mat[x + 1][y]))
				else:
					maxArr[x + 1][y] = max(maxArr[x][y], mat[x + 1][y])
				vis[x + 1][y] = 1
	return maxArr[-1][-1]
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return str(input())

def invr():
	return map(int, input().split())
T = inp()
for i in range(T):
	x = inlt()
	r = x[0]
	c = x[1]
	mat = []
	for i in range(r):
		mat.append(inlt())
	print(sol(r, c, mat))


for t in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	dp = []
	for i in range(n):
		curr = []
		for i in range(m):
			curr.append([0, 0])
		dp.append(curr)
	dp[-1][-1][0] = int(a[-1][-1])
	dp[-1][-1][1] = int(a[-1][-1])
	for i in range(n - 1, -1, -1):
		for j in range(m - 1, -1, -1):
			if i < n - 1 and j < m - 1:
				if a[i][j + 1] < a[i + 1][j]:
					target = (i + 1, j)
				else:
					target = (i, j + 1)
				dp[i][j][0] += max(a[i][j], dp[target[0]][target[1]][1])
			elif i < n - 1:
				target = (i + 1, j)
				dp[i][j][0] += max(a[i][j], dp[target[0]][target[1]][1])
			elif j < m - 1:
				target = (i, j + 1)
				dp[i][j][0] += max(a[i][j], dp[target[0]][target[1]][1])
			if i < n - 1 and j < m - 1:
				dp[i][j][1] += max(a[i][j], min(dp[i + 1][j][0], dp[i][j + 1][0]))
			elif i < n - 1:
				dp[i][j][1] += max(a[i][j], dp[i + 1][j][0])
			elif j < m - 1:
				dp[i][j][1] += max(a[i][j], dp[i][j + 1][0])
	print(dp[0][0][1])


from sys import setrecursionlimit
mod_ = 10 ** 9 + 7
setrecursionlimit(10 ** 7)

def f(i, j, n, m, a, flag, map_):
	if (i, j, flag) in map_:
		return map_[i, j, flag]
	if (i, j) == (n - 1, m - 1):
		return a[i][j]
	max_ = a[i][j]
	if i == n - 1:
		max_ = max(max_, f(i, j + 1, n, m, a, 0, map_))
		map_[i, j, flag] = max_
		return max_
	if j == m - 1:
		max_ = max(max_, f(i + 1, j, n, m, a, 0, map_))
		map_[i, j, flag] = max_
		return max_
	if not flag:
		cur = 0
		if a[i + 1][j] > a[i][j + 1]:
			cur = f(i + 1, j, n, m, a, 1, map_)
		else:
			cur = f(i, j + 1, n, m, a, 1, map_)
		max_ = max(max_, cur)
	else:
		max_ = max(max_, min(f(i + 1, j, n, m, a, 0, map_), f(i, j + 1, n, m, a, 0, map_)))
	map_[i, j, flag] = max_
	return max_
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = [0] * (n + 1)
	for i in range(n):
		a[i] = list(map(int, input().split())) + [0]
	a[n] = [0] * (m + 1)
	map_ = {}
	print(f(0, 0, n, m, a, 1, map_))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mat = []
	for _ in range(n):
		mat.append(list(map(int, input().split())))

	def valid(i, j):
		if 1 <= i <= n and 1 <= j <= m:
			return True
		return False

	def check(t):
		seen = set()
		q = [(1, 1, 0)]
		if mat[0][0] > t:
			return False
		while q:
			(x, y, v) = q.pop()
			if x == n and y == m:
				return True
			else:
				v1 = -float('inf')
				(a, b) = (-1, -1)
				for (dx, dy) in [(0, 1), (1, 0)]:
					(nx, ny) = (dx + x, dy + y)
					if v == 0:
						if valid(nx, ny) and mat[nx - 1][ny - 1] <= t and ((nx, ny, 1) not in seen):
							q.append((nx, ny, 1))
							seen.add((nx, ny, 1))
					else:
						v2 = -float('inf') if not valid(nx, ny) else mat[nx - 1][ny - 1]
						if v2 > v1:
							v1 = max(v1, v2)
							(a, b) = (nx, ny)
				if v != 0 and v1 <= t and ((a, b, 0) not in seen):
					q.append((a, b, 0))
					seen.add((a, b, 0))
		return False
	low = 0
	high = 10 ** 6
	while low <= high:
		mid = (low + high) // 2
		if check(mid):
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append(list(map(int, input().split())))
	dp = [[arr[i][j] for j in range(m)] for i in range(n)]
	for i in range(n - 2, -1, -1):
		dp[i][-1] = max(dp[i][-1], dp[i + 1][-1])
	for i in range(m - 2, -1, -1):
		dp[-1][i] = max(dp[-1][i], dp[-1][i + 1])
	for i in range(n - 2, -1, -1):
		for j in range(m - 2, -1, -1):
			if (i + j) % 2:
				if arr[i + 1][j] > arr[i][j + 1]:
					dp[i][j] = max(dp[i + 1][j], dp[i][j])
				else:
					dp[i][j] = max(dp[i][j + 1], dp[i][j])
			else:
				dp[i][j] = max(min(dp[i + 1][j], dp[i][j + 1]), dp[i][j])
	print(dp[0][0])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	grid = []
	for i in range(n):
		a = list(map(int, input().split()))
		grid.append(a)
	dp = [[0 for x in range(m + 1)] for j in range(n + 1)]
	for i in range(n - 1, -1, -1):
		for j in range(m - 1, -1, -1):
			if i == n - 1 and j == m - 1:
				dp[i][j] = grid[i][j]
			elif i == n - 1:
				dp[i][j] = max(grid[i][j], dp[i][j + 1])
			elif j == m - 1:
				dp[i][j] = max(grid[i][j], dp[i + 1][j])
			elif (i + j) % 2 == 0:
				dp[i][j] = max(grid[i][j], min(dp[i + 1][j], dp[i][j + 1]))
			elif grid[i + 1][j] > grid[i][j + 1]:
				dp[i][j] = max(grid[i][j], dp[i + 1][j])
			else:
				dp[i][j] = max(grid[i][j], dp[i][j + 1])
	print(dp[0][0])


import sys
sys.setrecursionlimit(10 ** 6)
t = int(input())

def getminval(grid, i, j, m, n, becky, cache):
	if (i, j) == (m - 1, n - 1):
		return grid[i][j]
	key = (becky, i, j)
	if key in cache:
		return cache[key]
	if i == m - 1:
		curr = getminval(grid, i, j + 1, m, n, not becky, cache)
		res = max(grid[i][j], curr)
		cache[key] = res
		return res
	if j == n - 1:
		curr = getminval(grid, i + 1, j, m, n, not becky, cache)
		res = max(grid[i][j], curr)
		cache[key] = res
		return res
	if becky:
		a = max(grid[i][j], getminval(grid, i + 1, j, m, n, not becky, cache))
		b = max(grid[i][j], getminval(grid, i, j + 1, m, n, not becky, cache))
		res = min(a, b)
		cache[key] = res
		return res
	elif grid[i + 1][j] > grid[i][j + 1]:
		curr = getminval(grid, i + 1, j, m, n, not becky, cache)
		res = max(grid[i][j], curr)
		cache[key] = res
		return res
	else:
		curr = getminval(grid, i, j + 1, m, n, not becky, cache)
		res = max(grid[i][j], curr)
		cache[key] = res
		return res
for _ in range(t):
	(m, n) = map(int, input().split())
	grid = []
	for __ in range(m):
		grid.append(list(map(int, input().split())))
	print(getminval(grid, 0, 0, m, n, True, {}))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	grid = []
	for i in range(n):
		grid.append(list(map(int, input().split())))
	dp = [[0] * m for i in range(n)]
	for i in range(n - 1, -1, -1):
		for j in range(m - 1, -1, -1):
			if j != m - 1:
				bla1 = grid[i][j + 1]
				(i1, j1) = (i, j + 1)
				if i1 + 1 < n and j1 + 1 < m:
					bla1 = max(bla1, dp[i1 + 1][j1]) if grid[i1 + 1][j1] >= grid[i1][j1 + 1] else max(bla1, dp[i1][j1 + 1])
				elif i1 + 1 < n:
					bla1 = max(bla1, dp[i1 + 1][j1])
				elif j1 + 1 < m:
					bla1 = max(bla1, dp[i1][j1 + 1])
				else:
					bla1 = bla1
			else:
				bla1 = float('inf') * -1
			if i != n - 1:
				bla2 = grid[i + 1][j]
				(i1, j1) = (i + 1, j)
				if i1 + 1 < n and j1 + 1 < m:
					bla2 = max(bla2, dp[i1 + 1][j1]) if grid[i1 + 1][j1] >= grid[i1][j1 + 1] else max(bla2, dp[i1][j1 + 1])
				elif i1 + 1 < n:
					bla2 = max(bla2, dp[i1 + 1][j1])
				elif j1 + 1 < m:
					bla2 = max(bla2, dp[i1][j1 + 1])
				else:
					bla2 = bla2
			else:
				bla2 = float('inf') * -1
			if i != n - 1 and j != m - 1:
				dp[i][j] = min(max(grid[i][j], bla1), max(grid[i][j], bla2))
			elif i != n - 1:
				dp[i][j] = max(grid[i][j], bla2)
			elif j != m - 1:
				dp[i][j] = max(grid[i][j], bla1)
			else:
				dp[i][j] = grid[i][j]
	print(dp[0][0])