Old Farmer Ranjan works on the farm of landlord Mittal Sahab. On the occasion of Diwali, Mittal Sahab decided to give some bonus to the hardworking farmer Ranjan. Mittal Sahab promised him to offer all the dragon fruits that Ranjan collects in one go from the right side of the farm returning back to the same side, such that he can take exactly 2 left turns.
Ranjan farmer can start plowing from any cell $A[i][N]$ where 1 ≤$ i$ ≤ N. 
The farm is represented as a 2D matrix, each cell consisting of some units of dragon fruit. Ranjan farmer wants to collect as much amount of dragon fruits as possible, but he is illiterate so he gave this job to his son, the great coder Rishi.
Please refer to the image below for more clarification on how to traverse the farm.

------ Input ------

The first line contains single integer $T$, denoting the number of test cases.
The next line consists of 2 space separated integers $N$ and $M$, denoting the dimension of the farm.
The next $N$ lines consist of $M$ space separated integers each denoting the amount of dragon fruit in the cell.

------ Output: ------
Output a single integer denoting the maximum amount of vegetable Ranjan farmer could collect.

------ Constraints  ------
$1 ≤ T ≤ 5$
$2 ≤ N,M ≤ 10^{3}$
$2 ≤ A[i][j] ≤ 10^{9}$ for  $1 ≤ i,j ≤ N,M respectively$

------ Sample Input: ------
	2
	3 3
	1 2 3
	3 3 1
	4 1 6
	3 3
	3 7 4
	1 9 6
	1 7 7

------ Sample Output: ------
	20
	34

Difficulty: VERY_HARD
Tags: Data structures

Range queries
Skill types: Data structures

Range queries

Starter code:

Solutions:
T = 0
try:
	T = int(input())
except:
	pass
while T > 0:
	(n, m) = map(int, input().split())
	contiguous_sum = [0] * m
	max_sum = 0
	while n > 0:
		row_vector = list(reversed(list(map(int, input().split()))))
		row_sum = 0
		for (i, k) in enumerate(row_vector):
			row_sum += k
			max_sum = max(max_sum, row_sum + contiguous_sum[i])
			contiguous_sum[i] = max(row_sum, k + contiguous_sum[i])
		n = n - 1
	print(max_sum)
	T = T - 1


for _ in range(int(input())):
	(r, c) = list(map(int, input().split()))
	(a, c1, msum) = ([], [0] * c, 0)
	for i in range(r):
		a = list(reversed(list(map(int, input().split()))))
		s = 0
		for (j, k) in enumerate(a):
			s += k
			msum = max(msum, s + c1[j])
			c1[j] = max(s, k + c1[j])
	print(msum)


a = int(input())
for i in range(a):
	cc = list(map(int, input().split()))
	prr = []
	for i in range(cc[0]):
		prr.append(list(map(int, input().split())))
	lrr = [[[0, 0] for i in range(cc[1])] for j in range(cc[0])]
	for i in range(cc[0]):
		trr = 0
		for j in range(cc[1] - 1, -1, -1):
			trr += prr[i][j]
			if i == 0:
				lrr[i][j][0] = trr
				lrr[i][j][1] = 0
			elif trr < lrr[i - 1][j][0] + prr[i][j]:
				lrr[i][j][0] = lrr[i - 1][j][0] + prr[i][j]
				lrr[i][j][1] = 0
			else:
				lrr[i][j][0] = trr
				lrr[i][j][1] = 1
	maxs = 0
	for i in range(1, cc[0]):
		trr = 0
		for j in range(cc[1] - 1, -1, -1):
			if lrr[i][j][1] == 0:
				if maxs < trr + lrr[i][j][0]:
					maxs = lrr[i][j][0] + trr
			elif maxs < trr + lrr[i - 1][j][0]:
				maxs = trr + lrr[i - 1][j][0] + prr[i][j]
			trr += prr[i][j]
	print(maxs)


import copy
for _ in range(int(input())):
	(n, m) = map(int, input().strip().split())
	s = []
	for __ in range(n):
		s.append(list(map(int, input().strip().split())))
	from_left = copy.deepcopy(s)
	from_right = copy.deepcopy(s)
	for i in range(n - 1, -1, -1):
		for j in range(m - 2, -1, -1):
			from_left[i][j] += from_left[i][j + 1]
	for i in range(n):
		for j in range(1, m):
			from_right[i][j] += from_right[i][j - 1]
	result = []
	for i in range(0, n):
		result.append([[0, 0]] * m)
		for j in range(m - 1, -1, -1):
			if i == 0:
				if j == m - 1:
					result[i][j] = [s[i][j], s[i][j]]
				else:
					result[i][j] = [s[i][j] + result[i][j + 1][1], s[i][j] + result[i][j + 1][1]]
			else:
				result[i][j] = [max(result[i - 1][j]) + s[i][j], from_left[i][j]]
	res = []
	for i in range(0, n):
		res.append([0] * m)
		for j in range(m - 1):
			res[i][j] = result[i][j][0] + from_left[i][j + 1]
	print(max((max(x) for x in res)))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	u = [0] * m
	r = 0
	for _ in range(n):
		vv = list(reversed(list(map(int, input().split()))))
		s = 0
		for (i, v) in enumerate(vv):
			s += v
			r = max(r, s + u[i])
			u[i] = max(s, v + u[i])
	print(r)


def T(x, y, d, n):
	try:
		f = lut[x, y, d]
	except KeyError:
		g = 0
	else:
		return f
	if d == 2:
		if y == n - 1:
			return a[x][y]
		else:
			k = a[x][y] + T(x, y + 1, 2, n)
			lut[x, y, d] = k
			return k
	elif d == 1:
		if x == 0:
			k = a[x][y] + T(x, y + 1, 2, n)
			lut[x, y, d] = k
			return k
		else:
			k = a[x][y] + max(T(x, y + 1, 2, n), T(x - 1, y, 1, n))
			lut[x, y, d] = k
			return k
	elif y == n - 1:
		k = a[x][y] + T(x, y - 1, 0, n)
		lut[x, y, d] = k
		return k
	elif y == 0:
		k = a[x][y] + T(x - 1, y, 1, n)
		lut[x, y, d] = k
		return k
	else:
		k = a[x][y] + max(T(x - 1, y, 1, n), T(x, y - 1, 0, n))
		lut[x, y, d] = k
		return k
for _ in range(int(input())):
	lut = {}
	(N, M) = [int(x) for x in input().split()]
	a = []
	for i in range(N):
		a += [[int(x) for x in input().split()]]
	ans = 0
	for i in range(1, N):
		ans = max(ans, T(i, M - 1, 0, M))
	print(ans)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	f1l = [[]] * n
	f2l = [[]] * n
	f3l = [[]] * n
	mat = [None] * n
	for i in range(n):
		f1l[i] = [0] * m
		f2l[i] = [0] * m
		f3l[i] = [0] * m
		mat[i] = list(map(int, input().split()))

	def f3(a, b):
		if a < n and a >= 0 and (b < m) and (b >= 0):
			if f3l[a][b] == 0:
				f3l[a][b] = mat[a][b] + f3(a, b + 1)
			return f3l[a][b]
		return 0

	def f2(a, b):
		if a < n and a >= 0 and (b < m) and (b >= 0):
			if f2l[a][b] == 0:
				f2l[a][b] = max(f2(a + 1, b) + mat[a][b], f3(a, b))
			return f2l[a][b]
		return 0

	def f1(a, b):
		if a < n and a >= 0 and (b < m) and (b >= 0):
			if f1l[a][b] == 0:
				f1l[a][b] = max(f1(a, b - 1) + mat[a][b], f2(a + 1, b) + mat[a][b])
			return f1l[a][b]
		return 0
	for i in range(n):
		x = f3(i, 0)
	for i in range(m):
		x = f2(0, i)
	(x, mx) = (0, 0)
	for i in range(n):
		x = f1(i, m - 1)
		if x > mx:
			mx = x
	print(mx)


from sys import stdin
for i in range(int(stdin.readline())):
	(n, m) = map(int, stdin.readline().split())
	f1l = [[]] * n
	f2l = [[]] * n
	f3l = [[]] * n
	mat = [None] * n
	for i in range(n):
		f1l[i] = [0] * m
		f2l[i] = [0] * m
		f3l[i] = [0] * m
		mat[i] = list(map(int, stdin.readline().split()))

	def f3(a, b):
		if a < n and a >= 0 and (b < m) and (b >= 0):
			if f3l[a][b] == 0:
				f3l[a][b] = mat[a][b] + f3(a, b + 1)
			return f3l[a][b]
		return 0

	def f2(a, b):
		if a < n and a >= 0 and (b < m) and (b >= 0):
			if f2l[a][b] == 0:
				f2l[a][b] = max(f2(a + 1, b) + mat[a][b], f3(a, b))
			return f2l[a][b]
		return 0

	def f1(a, b):
		if a < n and a >= 0 and (b < m) and (b >= 0):
			if f1l[a][b] == 0:
				f1l[a][b] = max(f1(a, b - 1) + mat[a][b], f2(a + 1, b) + mat[a][b])
			return f1l[a][b]
		return 0
	for i in range(n):
		x = f3(i, 0)
	for i in range(m):
		x = f2(0, i)
	(x, mx) = (0, 0)
	for i in range(n):
		x = f1(i, m - 1)
		if x > mx:
			mx = x
	print(mx)