C. Coin Rows

problem_index: C

time_limit: 2 seconds

memory_limit: 256 megabytes

note:
The paths for the testcases are shown on the following pictures. Alice's path is depicted in red and Bob's path is depicted in blue.
![image](images/cf_1555_C/1.png)

solutions: ["inf = 100000000000000000\n\ndef linput():\n\treturn list(map(int, input().split()))\nfor _ in range(int(input())):\n\tn = int(input())\n\tl1 = linput()\n\tl2 = linput()\n\tsuff1 = [l1[-1]]\n\tfor i in range(n - 2, -1, -1):\n\t\tsuff1.append(l1[i] + suff1[-1])\n\tsuff1 = suff1[::-1]\n\tpre2 = [l2[0]]\n\tfor i in range(1, n):\n\t\tpre2.append(l2[i] + pre2[-1])\n\tmini = inf\n\tfor i in range(n):\n\t\tval1 = suff1[i] - l1[i]\n\t\tval2 = pre2[i] - l2[i]\n\t\tmini = min(mini, max(val1, val2))\n\tprint(mini)\n", "import sys\n\ndef input():\n\treturn sys.stdin.readline().rstrip()\nDXY = [(0, -1), (1, 0), (0, 1), (-1, 0)]\n\ndef main():\n\tt = int(input())\n\tfor _ in range(t):\n\t\tn = int(input())\n\t\ta = [list(map(int, input().split())) for i in range(2)]\n\t\ta[0].reverse()\n\t\tb = [[0] * (n + 1) for i in range(2)]\n\t\tfor i in range(1, n + 1):\n\t\t\tb[0][i] = b[0][i - 1] + a[0][i - 1]\n\t\t\tb[1][i] = b[1][i - 1] + a[1][i - 1]\n\t\tans = min((max(b[0][i], b[1][n - 1 - i]) for i in range(n)))\n\t\tprint(ans)\n\treturn 0\nmain()\n", "import sys\nfor _ in range(int(input())):\n\tn = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tz = []\n\tz.append(a)\n\tz.append(b)\n\tsum1 = sum(a)\n\tans = sys.maxsize\n\tsum2 = 0\n\tfor i in range(n):\n\t\tsum1 -= z[0][i]\n\t\tans = min(ans, max(sum1, sum2))\n\t\tsum2 += z[1][i]\n\tprint(ans)\n", "import sys, os\nfrom math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log\nfrom collections import defaultdict\nif os.path.exists('input.txt'):\n\tsys.stdin = open('input.txt', 'r')\n\tsys.stdout = open('output.txt', 'w')\nfrom itertools import combinations\nfor _ in range(int(input())):\n\tn = int(input())\n\tA = list(map(int, input().split()))\n\tB = list(map(int, input().split()))\n\ts = 0\n\tif n == 1:\n\t\tprint(0)\n\t\tcontinue\n\tx = sum(A[1:])\n\tmx = x\n\ty = 0\n\tfor i in range(1, n):\n\t\tx -= A[i]\n\t\ty += B[i - 1]\n\t\tmx = min(mx, max(x, y))\n\tprint(mx)\n", "from __future__ import division, print_function\nimport os\nimport sys\nfrom io import BytesIO, IOBase\nif sys.version_info[0] < 3:\n\tfrom __builtin__ import xrange as range\n\tfrom future_builtins import ascii, filter, hex, map, oct, zip\n\ndef main():\n\tt = int(input())\n\tfor _ in range(t):\n\t\tm = int(input())\n\t\ta1 = [int(ai1) for ai1 in input().split()]\n\t\ta2 = [int(ai2) for ai2 in input().split()]\n\t\tpref_a1 = [0] * (m + 1)\n\t\tpref_a2 = [0] * (m + 1)\n\t\tfor i in range(m):\n\t\t\tpref_a1[i + 1] = pref_a1[i] + a1[i]\n\t\t\tpref_a2[i + 1] = pref_a2[i] + a2[i]\n\t\tsol = float('inf')\n\t\tfor i in range(m):\n\t\t\tsol = min(sol, max(pref_a1[-1] - pref_a1[i + 1], pref_a2[i]))\n\t\tprint(sol)\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n\ndef print(*args, **kwargs):\n\t(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))\n\tat_start = True\n\tfor x in args:\n\t\tif not at_start:\n\t\t\tfile.write(sep)\n\t\tfile.write(str(x))\n\t\tat_start = False\n\tfile.write(kwargs.pop('end', '\\n'))\n\tif kwargs.pop('flush', False):\n\t\tfile.flush()\nif sys.version_info[0] < 3:\n\t(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))\nelse:\n\t(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nmain()\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nfrom collections import *\nfrom collections import deque\nfrom operator import itemgetter, attrgetter\nfrom decimal import *\nimport bisect\nimport math\nimport heapq as hq\nMOD = 10 ** 9 + 7\n\ndef is_prime(n):\n\tif n == 2 or n == 3:\n\t\treturn True\n\tif n < 2 or n % 2 == 0:\n\t\treturn False\n\tif n < 9:\n\t\treturn True\n\tif n % 3 == 0:\n\t\treturn False\n\tr = int(n ** 0.5)\n\tf = 5\n\twhile f <= r:\n\t\tif n % f == 0:\n\t\t\treturn False\n\t\tif n % (f + 2) == 0:\n\t\t\treturn False\n\t\tf += 6\n\treturn True\n\ndef pow(a, b, m):\n\tans = 1\n\twhile b:\n\t\tif b & 1:\n\t\t\tans = ans * a % m\n\t\tb //= 2\n\t\ta = a * a % m\n\treturn ans\n\ndef ispalindrome(s):\n\tif s[:] == s[::-1]:\n\t\treturn 1\n\treturn 0\ndp = []\nlimit = []\nv = []\n\ndef dpdfs(u, t=-1):\n\tdp[0][u] = 0\n\tdp[1][u] = 0\n\tfor i in v[u]:\n\t\tif i == t:\n\t\t\tcontinue\n\t\tif dp[1][i] == -1:\n\t\t\tdpdfs(i, u)\n\t\tdp[0][u] += max(abs(limit[0][u] - limit[1][i]) + dp[1][i], abs(limit[0][u] - limit[0][i]) + dp[0][i])\n\t\tdp[1][u] += max(abs(limit[1][u] - limit[1][i]) + dp[1][i], abs(limit[1][u] - limit[0][i]) + dp[0][i])\nvis = []\nf = 0\n\ndef dfs(i):\n\tvis[i] = 1\n\tact[i] = 1\n\tfor j in v[i]:\n\t\tif act[j]:\n\t\t\tf = 1\n\t\t\treturn -1\n\t\tif vis[j] == 0:\n\t\t\tif dfs(j) == -1:\n\t\t\t\treturn -1\n\tact[i] = 0\n\tans.append(i)\n\treturn 0\nfrom queue import PriorityQueue\n\ndef z_algorithm(s):\n\tres = [0] * len(s)\n\tres[0] = len(s)\n\t(i, j) = (1, 0)\n\twhile i < len(s):\n\t\twhile i + j < len(s) and s[j] == s[i + j]:\n\t\t\tj += 1\n\t\tres[i] = j\n\t\tif j == 0:\n\t\t\ti += 1\n\t\t\tcontinue\n\t\tk = 1\n\t\twhile i + k < len(s) and k + res[k] < j:\n\t\t\tres[i + k] = res[k]\n\t\t\tk += 1\n\t\t(i, j) = (i + k, j - k)\n\treturn res\n\ndef gcd(a, b):\n\tif a == 0:\n\t\treturn b\n\treturn gcd(b % a, a)\n\ndef lcm(a, b):\n\treturn a / gcd(a, b) * b\n\ndef gcdExtended(a, b):\n\tif a == 0:\n\t\treturn (b, 0, 1)\n\t(gcd, x1, y1) = gcdExtended(b % a, a)\n\tx = y1 - b // a * x1\n\ty = x1\n\treturn (gcd, x, y)\nimport re\nfor _ in range(int(input())):\n\tn = int(input())\n\tl = []\n\tfor i in range(2):\n\t\tl.append(list(map(int, input().split())))\n\tans = math.inf\n\tl[0][0] = 0\n\tl[1][n - 1] = 0\n\tl[1].append(0)\n\tfor i in range(1, n):\n\t\tl[0][i] += l[0][i - 1]\n\t\tl[1][i] += l[1][i - 1]\n\tfor i in range(n):\n\t\tans = min(ans, max(l[0][n - 1] - l[0][i], l[1][i - 1]))\n\tprint(ans)\n", "for i in range(int(input())):\n\tn = int(input())\n\tarr = [int(i) for i in input().split()]\n\tbrr = [int(i) for i in input().split()]\n\tif n == 1:\n\t\tprint(0)\n\telif n == 2:\n\t\tprint(min(arr[1], brr[0]))\n\telse:\n\t\tfor i in range(1, n):\n\t\t\tarr[i] += arr[i - 1]\n\t\t\tbrr[i] += brr[i - 1]\n\t\tfor i in range(n):\n\t\t\tif i == 0:\n\t\t\t\tm = arr[-1] - arr[0]\n\t\t\telse:\n\t\t\t\tm = min(m, max(arr[-1] - arr[i], brr[i - 1]))\n\t\tprint(m)\n", "for _ in range(int(input())):\n\tm = int(input())\n\ts = [list(map(int, input().split())) for i in range(2)]\n\tfor i in range(1, m):\n\t\ts[0][m - i - 1] += s[0][m - i]\n\t\ts[1][i] += s[1][i - 1]\n\tif m == 1:\n\t\tprint(0)\n\telse:\n\t\tanswer = s[0][1]\n\t\tfor i in range(2, m):\n\t\t\ttmp = max(s[0][i], s[1][i - 2])\n\t\t\tanswer = min(tmp, answer)\n\t\tprint(min(answer, s[1][-2]))\n", "for case in range(int(input())):\n\tm = int(input())\n\ta = [[int(i) for i in input().split()] for i in range(2)]\n\ts1 = [0 for i in range(m)]\n\tfor i in range(m - 1, -1, -1):\n\t\ts1[i] = (s1[i + 1] if i + 1 < m else 0) + (a[0][i + 1] if i + 1 < m else 0)\n\ts2 = [0 for i in range(m)]\n\tfor i in range(m):\n\t\ts2[i] = (s2[i - 1] if i - 1 >= 0 else 0) + (a[1][i - 1] if i - 1 >= 0 else 0)\n\tans = float('inf')\n\tfor i in range(m):\n\t\tans = min(ans, max(s1[i], s2[i]))\n\tprint(ans)\n", "t = int(input())\nfor _ in range(t):\n\tm = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\ta_pred = [a[0]]\n\tb_pred = [b[0]]\n\tfor i in range(1, m):\n\t\ta_pred.append(a_pred[-1] + a[i])\n\t\tb_pred.append(b_pred[-1] + b[i])\n\tans = a_pred[-1] - a_pred[0]\n\tfor i in range(1, m):\n\t\tans = min(max(a_pred[-1] - a_pred[i], b_pred[i] - b[i]), ans)\n\tprint(ans)\n", "def coinRows(grid, m):\n\tgrid[0][0] = 0\n\tgrid[1][m - 1] = 0\n\tprefixSum = [[grid[i][j] for j in range(m)] for i in range(2)]\n\tsuffixSum = [[grid[i][j] for j in range(m)] for i in range(2)]\n\tfor i in range(1, m):\n\t\tprefixSum[0][i] += prefixSum[0][i - 1]\n\t\tprefixSum[1][i] += prefixSum[1][i - 1]\n\tfor i in range(m - 2, -1, -1):\n\t\tsuffixSum[0][i] += suffixSum[0][i + 1]\n\t\tsuffixSum[1][i] += suffixSum[1][i + 1]\n\tscore = float('inf')\n\tfor i in range(m):\n\t\tt = score\n\t\tif 1 <= i < m - 1:\n\t\t\tfirst = suffixSum[0][i + 1]\n\t\t\tsecond = prefixSum[1][i - 1]\n\t\t\tt = max(first, second)\n\t\telif i == 0 and i + 1 < m:\n\t\t\tt = suffixSum[0][i + 1]\n\t\telif i == m - 1 and i > 0:\n\t\t\tt = prefixSum[1][i - 1]\n\t\tscore = min(score, t)\n\treturn score if score != float('inf') else 0\nt = int(input())\nfor case in range(t):\n\tm = int(input())\n\tgrid = []\n\tfor i in range(2):\n\t\tgrid.append(list(map(int, input().split())))\n\tprint(coinRows(grid, m))\n", "t = int(input())\nfor i in range(t):\n\tm = int(input())\n\th = list(map(int, input().split()))\n\tl = list(map(int, input().split()))\n\tmaxi = 10 ** 10\n\thsum = sum(h)\n\tlsum = 0\n\tfor j in range(m):\n\t\thsum -= h[j]\n\t\tif j > 0:\n\t\t\tlsum += l[j - 1]\n\t\tmaxi = min(maxi, max(hsum, lsum))\n\tprint(maxi)\n", "import sys\nimport itertools\ncin = int(sys.stdin.readline().strip())\nfor testcase in range(cin):\n\tcin1 = int(sys.stdin.readline().strip())\n\tcin2 = list(map(int, sys.stdin.readline().strip().split()))\n\tcin3 = list(map(int, sys.stdin.readline().strip().split()))\n\ta1 = [0] + list(itertools.accumulate(cin2))\n\ta2 = [0] + list(itertools.accumulate(cin3))\n\tt1 = a1[-1]\n\tt2 = a2[-1]\n\ta = float('inf')\n\tfor i in range(len(a1)):\n\t\ta = min(a, max(t1 - a1[i], a2[i - 1]))\n\tprint(a)\n", "for _ in range(int(input())):\n\tm = int(input())\n\trow1 = list(map(int, input().split()))\n\trow2 = list(map(int, input().split()))\n\tscore = 10 ** 9\n\tsufix = sum(row1)\n\tprefix = 0\n\tfor i in range(m):\n\t\tsufix -= row1[i]\n\t\tscore = min(score, max(prefix, sufix))\n\t\tprefix += row2[i]\n\tprint(score)\n", "T = int(input())\nfor _ in range(T):\n\tn = int(input())\n\ta = []\n\ta.append(list(map(int, input().split())))\n\ta.append(list(map(int, input().split())))\n\t(s0, s1) = (sum(a[0]), sum(a[1]))\n\tres = [s0 - a[0][0]]\n\t(up, down) = (res[0], 0)\n\tfor i in range(1, n):\n\t\tup -= a[0][i]\n\t\tdown += a[1][i - 1]\n\t\tres.append(max(up, down))\n\tprint(min(res))\n", "for _ in range(int(input())):\n\tn = int(input())\n\tA = list(map(int, input().split()))\n\tB = list(map(int, input().split()))\n\ta = [0, sum(A[1:n])]\n\tans = max(a)\n\tfor i in range(1, n):\n\t\ta = [a[0] + B[i - 1], a[1] - A[i]]\n\t\tans = min(ans, max(a))\n\tprint(ans)\n", "import math\nt = int(input())\nfor _ in range(t):\n\tm = int(input())\n\tr1 = [int(i) for i in input().split()]\n\tr2 = [int(i) for i in input().split()]\n\tsum1 = sum(r1[1:])\n\tans = sum1\n\tsum2 = 0\n\tfor i in range(1, len(r1)):\n\t\tsum1 -= r1[i]\n\t\tsum2 += r2[i - 1]\n\t\tans = min(ans, max(sum1, sum2))\n\tprint(ans)\n", "t = int(input())\nfor _ in range(t):\n\tn = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tl = a.copy()\n\tl.reverse()\n\ts = 0\n\tfor i in range(n - 1):\n\t\ts = s + b[i]\n\tr = 0\n\tans = 0\n\tm = 0\n\tm = max(s, r)\n\tans = m\n\tfor i in range(n - 1):\n\t\tr = r + l[i]\n\t\ts = s - b[n - i - 2]\n\t\tm = max(s, r)\n\t\tif m < ans:\n\t\t\tans = m\n\tprint(ans)\n", "t = int(input())\nwhile t:\n\tt -= 1\n\tm = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tp1 = [0]\n\tp2 = [0]\n\tfor i in range(m):\n\t\tp1.append(p1[-1] + a[i])\n\t\tp2.append(p2[-1] + b[i])\n\tans = float('inf')\n\tfor i in range(m):\n\t\tans = min(ans, max(p1[-1] - p1[i + 1], p2[i]))\n\tprint(ans)\n", "def answer():\n\tN = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tSa = sum(a[1:])\n\tSb = 0\n\tans = Sa\n\tfor i in range(N - 1):\n\t\tSa -= a[i + 1]\n\t\tSb += b[i]\n\t\tans = min(max(Sa, Sb), ans)\n\tprint(ans)\nt = int(input())\nfor _ in range(t):\n\tanswer()\n", "t = int(input())\nfor _ in range(t):\n\tm = int(input())\n\tl1 = list(map(int, input().split()))\n\tl2 = list(map(int, input().split()))\n\tz1 = sum(l1)\n\tz2 = sum(l2)\n\tt = [z1 - l1[0], z2 - l2[-1]]\n\ta = z1 - l1[0]\n\tb = 0\n\tfor i in range(1, m - 1):\n\t\ta -= l1[i]\n\t\tb += l2[i - 1]\n\t\tt.append(max(a, b))\n\tprint(min(t))\n", "for _ in range(int(input())):\n\t(m, str_1, str_2) = (int(input()), list(map(int, input().split())), list(map(int, input().split())))\n\t(a, b) = (sum(str_1) - str_1[0], 0)\n\tans = a\n\tfor i in range(1, m):\n\t\ta -= str_1[i]\n\t\tb += str_2[i - 1]\n\t\tans = min(max(a, b), ans)\n\tprint(ans)\n", "import sys\nimport math\n\ndef inpu():\n\treturn sys.stdin.readline()\nT = int(input())\nfor t in range(T):\n\tn = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tdone = False\n\tsa = sum(a) - a[0]\n\tans = sa\n\tsb = 0\n\tfor i in range(1, n):\n\t\tsa -= a[i]\n\t\tsb += b[i - 1]\n\t\tans = min(ans, max(sa, sb))\n\tprint(ans)\n", "def solve(m, arr):\n\t(s1, s2) = (0, sum(arr[1]) - arr[1][-1])\n\tlow = s2\n\tfor i in range(m - 1)[::-1]:\n\t\t(s1, s2) = (s1 + arr[0][i + 1], s2 - arr[1][i])\n\t\tlow = min(low, max(s1, s2))\n\treturn low\n\ndef main():\n\tfor _ in range(int(input())):\n\t\tm = int(input())\n\t\tarr = [[*map(int, input().split(' '))] for _ in range(2)]\n\t\tprint(solve(m, arr))\nmain()\n", "import sys\ninput = sys.stdin.readline\n\ndef solve():\n\tn = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tsa = sum(a) - a[0]\n\tsb = 0\n\tr = sa\n\tfor i in range(1, n):\n\t\tsa -= a[i]\n\t\tsb += b[i - 1]\n\t\tr = min(r, max(sa, sb))\n\tprint(r)\nfor i in range(int(input())):\n\tsolve()\n", "import sys, os, io\nfrom sys import stdin\nimport math\nfrom collections import defaultdict\nfrom heapq import heappush, heappop, heapify\nfrom bisect import bisect_left, bisect_right\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\nalphabets = list('abcdefghijklmnopqrstuvwxyz')\nfrom types import GeneratorType\n\ndef bootstrap(f, stack=[]):\n\n\tdef wrappedfunc(*args, **kwargs):\n\t\tif stack:\n\t\t\treturn f(*args, **kwargs)\n\t\telse:\n\t\t\tto = f(*args, **kwargs)\n\t\t\twhile True:\n\t\t\t\tif type(to) is GeneratorType:\n\t\t\t\t\tstack.append(to)\n\t\t\t\t\tto = next(to)\n\t\t\t\telse:\n\t\t\t\t\tstack.pop()\n\t\t\t\t\tif not stack:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tto = stack[-1].send(to)\n\t\t\treturn to\n\treturn wrappedfunc\n\ndef ncr(n, r, p):\n\tnum = den = 1\n\tfor i in range(r):\n\t\tnum = num * (n - i) % p\n\t\tden = den * (i + 1) % p\n\treturn num * pow(den, p - 2, p) % p\n\ndef primeFactors(n):\n\tl = []\n\twhile n % 2 == 0:\n\t\tl.append(2)\n\t\tn = n / 2\n\tfor i in range(3, int(math.sqrt(n)) + 1, 2):\n\t\twhile n % i == 0:\n\t\t\tl.append(int(i))\n\t\t\tn = n / i\n\tif n > 2:\n\t\tl.append(n)\n\treturn list(set(l))\n\ndef power(x, y, p):\n\tres = 1\n\tx = x % p\n\tif x == 0:\n\t\treturn 0\n\twhile y > 0:\n\t\tif y & 1 == 1:\n\t\t\tres = res * x % p\n\t\ty = y >> 1\n\t\tx = x * x % p\n\treturn res\n\ndef sieveForSmallestPrimeFactor():\n\tMAXN = 100001\n\tspf = [0 for i in range(MAXN)]\n\tspf[1] = 1\n\tfor i in range(2, MAXN):\n\t\tspf[i] = i\n\tfor i in range(4, MAXN, 2):\n\t\tspf[i] = 2\n\tfor i in range(3, math.ceil(math.sqrt(MAXN))):\n\t\tif spf[i] == i:\n\t\t\tfor j in range(i * i, MAXN, i):\n\t\t\t\tif spf[j] == j:\n\t\t\t\t\tspf[j] = i\n\treturn spf\n\ndef getPrimeFactorizationLOGN(x):\n\tspf = sieveForSmallestPrimeFactor()\n\tret = list()\n\twhile x != 1:\n\t\tret.append(spf[x])\n\t\tx = x // spf[x]\n\treturn ret\n\ndef SieveOfEratosthenes(n):\n\tprime = [True for i in range(n + 1)]\n\tp = 2\n\twhile p * p <= n:\n\t\tif prime[p] == True:\n\t\t\tfor i in range(p * p, n + 1, p):\n\t\t\t\tprime[i] = False\n\t\tp += 1\n\treturn prime\n\ndef si():\n\treturn input()\n\ndef divideCeil(n, x):\n\tif n % x == 0:\n\t\treturn n // x\n\treturn n // x + 1\n\ndef ii():\n\treturn int(input())\n\ndef li():\n\treturn list(map(int, input().split()))\nif os.path.exists('input.txt'):\n\tsys.stdin = open('input.txt', 'r')\n\tsys.stdout = open('output.txt', 'w')\nelse:\n\t(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\n\tinput = lambda : sys.stdin.readline().rstrip('\\r\\n')\n\ndef solve():\n\tn = ii()\n\tl = []\n\tfor i in range(2):\n\t\tl.append(li())\n\tif n == 1:\n\t\tprint(0)\n\t\treturn\n\tu = [0] * n\n\td = [0] * n\n\tu[-1] = l[0][-1]\n\tfor i in range(n - 2, -1, -1):\n\t\tu[i] += u[i + 1] + l[0][i]\n\td[0] = l[1][0]\n\tfor i in range(1, n):\n\t\td[i] += d[i - 1] + l[1][i]\n\tans = float('inf')\n\tfor i in range(1, n - 1):\n\t\tans = min(ans, max(d[i - 1], u[i + 1]))\n\tans = min(ans, d[-2], u[1])\n\tprint(ans)\nt = 1\nt = ii()\nfor _ in range(t):\n\tsolve()\n", "for _ in range(int(input())):\n\tm = int(input())\n\ts1 = list(map(int, input().split()))\n\ts2 = list(map(int, input().split()))\n\ts1[0] = 0\n\ts2[-1] = 0\n\tS1 = sum(s1)\n\tS2 = 0\n\tmn = max(S2, S1)\n\tfor i in range(1, m):\n\t\tS1 -= s1[i]\n\t\tS2 += s2[i - 1]\n\t\tmn = min(mn, max(S2, S1))\n\tprint(mn)\n", "import sys\ninput = sys.stdin.readline\n\ndef inp():\n\treturn int(input())\n\ndef inlt():\n\treturn list(map(int, input().split()))\nT = inp()\nfor i in range(T):\n\tm = inp()\n\tl1 = inlt()\n\tl2 = inlt()\n\tif m == 1:\n\t\tprint(0)\n\telif m == 2:\n\t\tprint(min(l1[1], l2[0]))\n\telse:\n\t\tsum_row1 = {}\n\t\tsum_row2 = {}\n\t\tsum_row1[0] = l1[0]\n\t\tsum_row2[0] = l2[0]\n\t\tfor j in range(1, m):\n\t\t\tsum_row1[j] = l1[j] + sum_row1[j - 1]\n\t\t\tsum_row2[j] = l2[j] + sum_row2[j - 1]\n\t\tmax_score = sum_row1[m - 1] - sum_row1[0]\n\t\tindex = 0\n\t\tfor p in range(1, m):\n\t\t\tscore = max(sum_row1[m - 1] - sum_row1[p], sum_row2[p - 1])\n\t\t\tif score < max_score:\n\t\t\t\tmax_score = score\n\t\t\t\tindex = p\n\t\tif index == 0:\n\t\t\tprint(sum_row1[m - 1] - sum_row1[0])\n\t\telif index == m - 1:\n\t\t\tprint(sum_row2[m - 2])\n\t\telse:\n\t\t\tprint(max(sum_row1[m - 1] - sum_row1[index], sum_row2[index - 1]))\n", "from collections import defaultdict, deque, Counter\nfrom sys import stdin, stdout\nfrom heapq import heappush, heappop\nimport math\nimport io\nimport os\nimport math\nimport bisect\n\ndef isPrime(x):\n\tfor i in range(2, x):\n\t\tif i * i > x:\n\t\t\tbreak\n\t\tif x % i == 0:\n\t\t\treturn False\n\treturn True\n\ndef ncr(n, r, p):\n\tnum = den = 1\n\tfor i in range(r):\n\t\tnum = num * (n - i) % p\n\t\tden = den * (i + 1) % p\n\treturn num * pow(den, p - 2, p) % p\n\ndef primeFactors(n):\n\tl = []\n\twhile n % 2 == 0:\n\t\tl.append(2)\n\t\tn = n / 2\n\tfor i in range(3, int(math.sqrt(n)) + 1, 2):\n\t\twhile n % i == 0:\n\t\t\tl.append(int(i))\n\t\t\tn = n / i\n\tif n > 2:\n\t\tl.append(n)\n\treturn list(set(l))\n\ndef power(x, y, p):\n\tres = 1\n\tx = x % p\n\tif x == 0:\n\t\treturn 0\n\twhile y > 0:\n\t\tif y & 1 == 1:\n\t\t\tres = res * x % p\n\t\ty = y >> 1\n\t\tx = x * x % p\n\treturn res\n\ndef sieve(n):\n\tprime = [True for i in range(n + 1)]\n\tp = 2\n\twhile p * p <= n:\n\t\tif prime[p] == True:\n\t\t\tfor i in range(p * p, n + 1, p):\n\t\t\t\tprime[i] = False\n\t\tp += 1\n\treturn prime\n\ndef digits(n):\n\tc = 0\n\twhile n > 0:\n\t\tn //= 10\n\t\tc += 1\n\treturn c\n\ndef ceil(n, x):\n\tif n % x == 0:\n\t\treturn n // x\n\treturn n // x + 1\n\ndef mapin():\n\treturn [int(i) for i in input().split()]\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\nt = int(input())\nfor _ in range(t):\n\tm = int(input())\n\td = []\n\ta = mapin()\n\td.append(a)\n\tb = mapin()\n\td.append(b)\n\tans = 1e+20\n\tpre = [0] * m\n\tpre2 = [0] * m\n\ttemp = 0\n\ttemp2 = 0\n\tfor i in range(m):\n\t\ttemp += d[0][i]\n\t\tpre[i] = temp\n\t\tpre2[i] = temp2\n\t\ttemp2 += d[1][i]\n\ttemp = 0\n\ttemp2 = 0\n\tfor i in range(m - 1, -1, -1):\n\t\ttemp += d[1][i]\n\t\tpre[i] += temp\n\t\tpre2[i] = max(pre2[i], temp2)\n\t\ttemp2 += d[0][i]\n\tprint(min(pre2))\n", "import sys\ninput = sys.stdin.readline\nfor _ in range(int(input())):\n\tm = int(input())\n\ta = []\n\tfor i in range(2):\n\t\ta.append(list(map(int, input().split())))\n\tans = 1000000000000000.0\n\tsum1 = sum2 = 0\n\tfor i in range(m):\n\t\tsum1 += a[0][i]\n\tfor i in range(m):\n\t\tsum1 -= a[0][i]\n\t\tans = min(ans, max(sum1, sum2))\n\t\tsum2 += a[1][i]\n\tprint(ans)\n", "import sys\ntokens = ''.join(sys.stdin.readlines()).split()[::-1]\n\ndef next():\n\treturn tokens.pop()\n\ndef nextInt():\n\treturn int(next())\n\ndef nextFloat():\n\treturn float(next())\n\ndef getIntArray(n):\n\treturn [nextInt() for _ in range(n)]\n\ndef getFloatArray(n):\n\treturn [nextFloat() for _ in range(n)]\n\ndef getStringArray(n):\n\treturn [next() for _ in range(n)]\nflush = sys.stdout.flush\ntestcase = True\n\ndef solve(testcase):\n\tN = nextInt()\n\tA = [getIntArray(N), getIntArray(N)]\n\t(S1, S2) = (sum(A[0]), 0)\n\tfinalScore = max(S1 - A[0][0], sum(A[1]) - A[-1][-1])\n\tfor i in range(N):\n\t\tS1 -= A[0][i]\n\t\tscore = max(S1, S2)\n\t\tS2 += A[1][i]\n\t\tfinalScore = min(finalScore, score)\n\tprint(finalScore)\ntestcaseCount = nextInt() if testcase else 1\nfor tc in range(testcaseCount):\n\tsolve(tc + 1)\nassert not tokens\n", "for _ in range(int(input())):\n\tn = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tfor i in range(1, n):\n\t\tb[i] += b[i - 1]\n\t\ta[i] += a[i - 1]\n\tans = 10 ** 12\n\tb.append(0)\n\tfor i in range(n):\n\t\tans = min(ans, max(a[n - 1] - a[i], b[i - 1]))\n\tprint(ans)\n", "n = int(input())\nfor _ in range(n):\n\tm = int(input())\n\trow = [list(map(int, input().split()))]\n\trow += [list(map(int, input().split()))]\n\trow[0][0] = 0\n\trow[1][-1] = 0\n\tsum_row_0 = sum(row[0])\n\tsum_row_1 = 0\n\tfinal_score = sum_row_0\n\tfor i in range(1, m):\n\t\tif m == 1:\n\t\t\tfinal_score = 0\n\t\t\tbreak\n\t\tif m == 2:\n\t\t\tfinal_score = min(sum(row[0]), sum(row[1]))\n\t\t\tbreak\n\t\tsum_row_0 -= row[0][i]\n\t\tsum_row_1 += row[1][i - 1]\n\t\tcurrenty_score = max(sum_row_0, sum_row_1)\n\t\tif currenty_score < final_score:\n\t\t\tfinal_score = currenty_score\n\t\t\tif i == m - 1:\n\t\t\t\tbreak\n\t\telse:\n\t\t\tbreak\n\tprint(final_score)\n", "for _ in range(int(input())):\n\tm = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tif m == 1:\n\t\tprint(0)\n\t\tcontinue\n\tsuma = sum(a) - a[0]\n\tsumb = 0\n\tminn = suma\n\tfor i in range(1, m):\n\t\tsuma -= a[i]\n\t\tsumb += b[i - 1]\n\t\tminn = min(minn, max(suma, sumb))\n\tprint(minn)\n", "import itertools\nt = int(input())\nfor h in range(t):\n\tm = int(input())\n\ta = list(([], []))\n\ta[0] = list(map(int, input().split()))\n\ta[0].append(0)\n\ta[1] = list(map(int, input().split()))\n\ta[1].insert(0, 0)\n\ta[0] = a[0][::-1]\n\tk1 = list(itertools.accumulate(a[0]))\n\tk1.pop()\n\tk2 = list(itertools.accumulate(a[1]))\n\tk2.pop()\n\tk2 = k2[::-1]\n\ts = list(zip(k1, k2))\n\ts = min(list(map(max, s)))\n\tprint(s)\n", "def get_ans(mas1, mas2, m):\n\tsum1 = sum(mas1)\n\tsum2 = 0\n\tmaxs = []\n\tfor i in range(m):\n\t\tsum1 -= mas1[i]\n\t\tmaxs.append(max(sum1, sum2))\n\t\tsum2 += mas2[i]\n\treturn min(maxs)\n\ndef main():\n\tn = int(input())\n\tfor i in range(n):\n\t\tm = int(input())\n\t\tmas1 = list(map(int, input().split()))\n\t\tmas2 = list(map(int, input().split()))\n\t\tres = get_ans(mas1, mas2, m)\n\t\tprint(res)\nmain()\n", "import sys\ninput = sys.stdin.readline\nfor _ in range(int(input())):\n\tm = int(input())\n\tcoins = [[int(i) for i in input().split()] for j in range(2)]\n\t(row1, row2, ans) = (sum(coins[0]), 0, float('inf'))\n\tfor i in range(m):\n\t\trow1 -= coins[0][i]\n\t\tif i != 0:\n\t\t\trow2 += coins[1][i - 1]\n\t\tans = min(ans, max(row1, row2))\n\tprint(ans)\n", "for _ in range(int(input())):\n\tn = int(input())\n\ta = [list(map(int, input().split())) for i in range(2)]\n\tdp = [i[:] for i in a]\n\tfor i in range(1, n):\n\t\tdp[0][i] += dp[0][i - 1]\n\tfor i in range(n - 2, -1, -1):\n\t\tdp[1][i] += dp[1][i + 1]\n\tres = float('inf')\n\tfor i in range(n):\n\t\tres = min(res, max(dp[0][n - 1] - dp[0][i], dp[1][0] - dp[1][i]))\n\tprint(res)\n", "tes = int(input())\nfor _ in range(tes):\n\ttestnumber = int(input())\n\ttemp1 = [int(i) for i in input().split()]\n\ttemp2 = [int(i) for i in input().split()]\n\tthevalueforqianzhuihe = []\n\tthevalueforhouzhuihe = []\n\tfor i in range(2):\n\t\tthevalueforqianzhuihe.append([])\n\t\tfor j in range(testnumber):\n\t\t\tthevalueforqianzhuihe[i].append(0)\n\tfor i in range(2):\n\t\tthevalueforhouzhuihe.append([])\n\t\tfor j in range(testnumber):\n\t\t\tthevalueforhouzhuihe[i].append(0)\n\tthevaluefortestcase = [temp1, temp2]\n\tfor i in range(2):\n\t\tisqianzhuihe = 0\n\t\tishouzhuihe = 0\n\t\tfor j in range(testnumber):\n\t\t\tthevalueforqianzhuihe[i][j] = isqianzhuihe\n\t\t\tisqianzhuihe = isqianzhuihe + thevaluefortestcase[i][j]\n\t\tfor j in range(testnumber - 1, -1, -1):\n\t\t\tthevalueforhouzhuihe[i][j] = ishouzhuihe\n\t\t\tishouzhuihe = ishouzhuihe + thevaluefortestcase[i][j]\n\tminoffinal = 10000000000.0\n\tfor i in range(testnumber):\n\t\tminoffinal = min(minoffinal, max(thevalueforhouzhuihe[0][i], thevalueforqianzhuihe[1][i]))\n\tprint(minoffinal)\n", "t = int(input())\nfor i in range(t):\n\tc = []\n\tn = int(input())\n\tp = [int(x) for x in input().split()]\n\tp1 = [int(x) for x in input().split()]\n\tif n == 1:\n\t\tprint(0)\n\t\tcontinue\n\ts = sum(p) - p[0]\n\ts1 = 0\n\tmi = max(s, s1)\n\tfor j in range(1, n):\n\t\ts -= p[j]\n\t\ts1 += p1[j - 1]\n\t\tmx = max(s, s1)\n\t\tif mi > mx:\n\t\t\tmi = mx\n\tprint(mi)\n", "t = int(input())\nfor i in range(0, t):\n\tm = int(input())\n\tlist1 = list(map(int, input().split()))\n\tlist2 = list(map(int, input().split()))\n\tsumlist = []\n\tarr = []\n\tarr.append(list1)\n\tarr.append(list2)\n\tsum1 = 0\n\tsum2 = 0\n\tfor i in range(1, len(list1)):\n\t\tsum1 = sum1 + list1[i]\n\tsumlist.append(max(sum1, sum2))\n\tfor i in range(1, len(list1)):\n\t\tsum1 = sum1 - list1[i]\n\t\tsum2 = sum2 + list2[i - 1]\n\t\tsumlist.append(max(sum1, sum2))\n\tprint(min(sumlist))\n", "import os, sys, math\nfrom io import BytesIO, IOBase\nfrom collections import defaultdict, deque, OrderedDict\nimport bisect as bi\n\ndef yes():\n\tprint('YES')\n\ndef no():\n\tprint('NO')\n\ndef I():\n\treturn int(input())\n\ndef In():\n\treturn map(int, input().split())\n\ndef ln():\n\treturn list(map(int, input().split()))\n\ndef Sn():\n\treturn input().strip()\nBUFSIZE = 8192\n\ndef find_gt(a, x):\n\ti = bi.bisect_left(a, x)\n\tif i != len(a):\n\t\treturn i\n\telse:\n\t\treturn len(a)\n\ndef solve():\n\tn = I()\n\ta = list(In())\n\tb = list(In())\n\t(pre_a, pre_b) = ([0], [0])\n\tfor i in range(n):\n\t\tpre_a.append(pre_a[-1] + a[i])\n\t\tpre_b.append(pre_b[-1] + b[i])\n\tans = 0\n\tfor i in range(1, n + 1):\n\t\t(suf, pre) = (pre_a[-1] - pre_a[i], pre_b[i])\n\t\tans = max(ans, min(suf, pre))\n\tprint(ans)\n\tpass\n\ndef main():\n\tT = I()\n\tfor i in range(T):\n\t\tsolve()\nM = 998244353\nP = 1000000007\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nmain()\n", "from collections import deque as de\nimport math\nfrom math import sqrt as sq\nfrom math import floor as fl\nfrom math import ceil as ce\nfrom sys import stdin, stdout\nimport re\nfrom collections import Counter as cnt\nfrom functools import reduce\nfrom itertools import groupby as gb\nfrom bisect import bisect_left as bl, bisect_right as br\n\ndef factors(n):\n\treturn set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))\n\nclass My_stack:\n\n\tdef __init__(self):\n\t\tself.data = []\n\n\tdef my_push(self, x):\n\t\treturn self.data.append(x)\n\n\tdef my_pop(self):\n\t\treturn self.data.pop()\n\n\tdef my_peak(self):\n\t\treturn self.data[-1]\n\n\tdef my_contains(self, x):\n\t\treturn self.data.count(x)\n\n\tdef my_show_all(self):\n\t\treturn self.data\n\n\tdef isEmpty(self):\n\t\treturn len(self.data) == 0\narrStack = My_stack()\n\ndef decimalToBinary(n):\n\treturn bin(n).replace('0b', '')\n\ndef binarytodecimal(n):\n\treturn int(n, 2)\n\ndef isPrime(n):\n\tif n <= 1:\n\t\treturn False\n\tif n <= 3:\n\t\treturn True\n\tif n % 2 == 0 or n % 3 == 0:\n\t\treturn False\n\ti = 5\n\twhile i * i <= n:\n\t\tif n % i == 0 or n % (i + 2) == 0:\n\t\t\treturn False\n\t\ti = i + 6\n\treturn True\n\ndef get_prime_factors(number):\n\tprime_factors = []\n\twhile number % 2 == 0:\n\t\tprime_factors.append(2)\n\t\tnumber = number / 2\n\tfor i in range(3, int(math.sqrt(number)) + 1, 2):\n\t\twhile number % i == 0:\n\t\t\tprime_factors.append(int(i))\n\t\t\tnumber = number / i\n\tif number > 2:\n\t\tprime_factors.append(int(number))\n\treturn prime_factors\n\ndef get_frequency(list):\n\tdic = {}\n\tfor ele in list:\n\t\tif ele in dic:\n\t\t\tdic[ele] += 1\n\t\telse:\n\t\t\tdic[ele] = 1\n\treturn dic\n\ndef Log2(x):\n\treturn math.log10(x) / math.log10(2)\n\ndef getProduct(n):\n\tproduct = 1\n\twhile n != 0:\n\t\tproduct = product * (n % 10)\n\t\tn = n // 10\n\treturn product\n\ndef lcm(x, y):\n\tlcm = x * y // math.gcd(x, y)\n\treturn lcm\n\ndef isPowerOfTwo(n):\n\treturn math.ceil(Log2(n)) == math.floor(Log2(n))\n\ndef checkisap(list):\n\td = list[1] - list[0]\n\tfor i in range(2, len(list)):\n\t\ttemp = list[i] - list[i - 1]\n\t\tif temp != d:\n\t\t\treturn False\n\treturn True\n\ndef primes_method5(n):\n\tout = {}\n\tsieve = [True] * (n + 1)\n\tfor p in range(2, n + 1):\n\t\tif sieve[p]:\n\t\t\tout[p] = 1\n\t\t\tfor i in range(p, n + 1, p):\n\t\t\t\tsieve[i] = False\n\treturn out\n\ndef getSum(n):\n\tstrr = str(n)\n\tlist_of_number = list(map(int, strr.strip()))\n\treturn sum(list_of_number)\n\ndef ceildiv(x, y):\n\treturn (x + y - 1) // y\n\ndef di():\n\treturn map(int, input().split())\n\ndef ii():\n\treturn int(input())\n\ndef li():\n\treturn list(map(int, input().split()))\n\ndef si():\n\treturn list(map(str, input()))\n\ndef indict():\n\tdic = {}\n\tfor (index, value) in enumerate(input().split()):\n\t\tdic[int(value)] = int(index) + 1\n\treturn dic\n\ndef frqdict():\n\tdic = {}\n\tfor (index, value) in enumerate(input()):\n\t\tif value not in dic:\n\t\t\tdic[value] = 1\n\t\telse:\n\t\t\tdic[value] += 1\n\treturn dic\nt = ii()\nwhile t:\n\tt -= 1\n\tn = ii()\n\ta = li()\n\tb = li()\n\tif n == 1:\n\t\tprint(0)\n\telif n == 2:\n\t\tprint(min(a[1], b[0]))\n\telse:\n\t\tsumb = sum(b)\n\t\tsuma = sum(a)\n\t\ttempa = suma - a[0]\n\t\ttempb = 0\n\t\tmn = max(tempa, tempb)\n\t\tfor i in range(1, n):\n\t\t\ttempa -= a[i]\n\t\t\ttempb += b[i - 1]\n\t\t\ttempmax = max(tempa, tempb)\n\t\t\tif tempmax < mn:\n\t\t\t\tmn = tempmax\n\t\tprint(mn)\n", "t = int(input())\nfor i in range(t):\n\tn = int(input())\n\tlsta = list(map(int, input().split()))\n\tlstb = list(map(int, input().split()))\n\tprea = [lsta[0]]\n\tpreb = [lstb[0]]\n\tfor j in range(1, n):\n\t\tprea.append(prea[-1] + lsta[j])\n\t\tpreb.append(preb[-1] + lstb[j])\n\ta = prea[-1] - prea[0]\n\tb = 0\n\tdif = a - b\n\tind = 1\n\tlst1 = [max(a, b)]\n\twhile True:\n\t\tif dif <= 0:\n\t\t\tbreak\n\t\telse:\n\t\t\ta = prea[-1] - prea[ind]\n\t\t\tb = preb[ind - 1]\n\t\t\tdif = a - b\n\t\t\tlst1.append(max(a, b))\n\t\t\tind += 1\n\tif lst1 == []:\n\t\tprint(0)\n\telse:\n\t\tprint(min(lst1))\n", "import math\nfor _ in range(int(input())):\n\tn = int(input())\n\tl1 = list(map(int, input().split()))\n\tl2 = list(map(int, input().split()))\n\tif n == 1:\n\t\tprint(0)\n\t\tcontinue\n\tpref = [0] * n\n\tsuff = [0] * n\n\tc = math.inf\n\tpref[0] = l1[0]\n\tsuff[0] = l2[0]\n\tfor x in range(1, n):\n\t\tpref[x] += pref[x - 1] + l1[x]\n\t\tsuff[x] += suff[x - 1] + l2[x]\n\tfor x in range(1, n - 1):\n\t\tk = max(pref[-1] - pref[x], suff[x - 1])\n\t\tc = min(c, k)\n\tc = min(c, pref[-1] - pref[0])\n\tc = min(c, suff[-2])\n\tprint(c)\n", "import sys\nimport math\nimport collections\nfrom os import path\nfrom collections import defaultdict\nmod = 10 ** 9 + 7\nsys.setrecursionlimit(10 ** 6)\nif path.exists('input.txt'):\n\tsys.stdin = open('input.txt', 'r')\n\tsys.stdout = open('output.txt', 'w')\ntest = int(sys.stdin.readline().rstrip())\nwhile test > 0:\n\ttest -= 1\n\tn = int(sys.stdin.readline().rstrip())\n\ta = list(map(int, sys.stdin.readline().rstrip().split()))\n\tb = list(map(int, sys.stdin.readline().rstrip().split()))\n\tif n == 1:\n\t\tprint(0)\n\telse:\n\t\ta1 = [0] * n\n\t\ts = 0\n\t\tfor x in range(n):\n\t\t\ts += a[x]\n\t\t\ta1[x] = s\n\t\tb1 = [0] * n\n\t\ts = 0\n\t\tfor x in range(n - 1, -1, -1):\n\t\t\ts += b[x]\n\t\t\tb1[x] = s\n\t\tans = 10 ** 10\n\t\tfor x in range(n):\n\t\t\tp = max(a1[n - 1] - a1[x], b1[0] - b1[x])\n\t\t\tif p < ans:\n\t\t\t\tans = p\n\t\tprint(ans)\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nfrom itertools import accumulate\nnmbr = lambda : int(input())\nlst = lambda : list(map(int, input().split()))\n\ndef main():\n\tfor _ in range(nmbr()):\n\t\tn = nmbr()\n\t\tf = lst()\n\t\ts = lst()\n\t\tpre = list(accumulate(f))\n\t\tsuf = list(accumulate(s[::-1]))[::-1]\n\t\tans = float('inf')\n\t\tfor i in range(n):\n\t\t\tleft = pre[i]\n\t\t\tright = suf[i]\n\t\t\tm1 = pre[-1] - left\n\t\t\tm2 = suf[0] - right\n\t\t\tans = min(ans, max(m1, m2))\n\t\tsys.stdout.write(str(ans) + '\\n')\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nfor t in range(1):\n\tmain()\n", "for _ in range(int(input())):\n\tm = int(input())\n\trow1 = [int(x) for x in input().split()]\n\trow2 = [int(x) for x in input().split()]\n\ts1 = sum(row1)\n\ts2 = sum(row2)\n\talice = 0\n\tbob = 10000000000\n\tpref_sums1 = [0] * (m + 1)\n\tpref_sums2 = [0] * (m + 1)\n\tfor i in range(m):\n\t\tpref_sums1[i + 1] = pref_sums1[i] + row1[i]\n\t\tpref_sums2[i + 1] = pref_sums2[i] + row2[i]\n\tfor i in range(m):\n\t\ta = pref_sums1[i + 1] + pref_sums2[m] - pref_sums2[i]\n\t\tb = max(s1 - pref_sums1[i + 1], s2 - (pref_sums2[m] - pref_sums2[i]))\n\t\tif bob > b:\n\t\t\tbob = b\n\tprint(bob)\n", "import sys\ninput = sys.stdin.readline\nfor _ in range(int(input())):\n\t(n, arr) = (int(input()), [])\n\tfor _ in range(2):\n\t\tarr.append(list(map(int, input().split())))\n\tmx = 1000000000000000.0\n\tsum1 = sum2 = 0\n\tfor i in range(n):\n\t\tsum1 += arr[0][i]\n\tfor i in range(n):\n\t\tsum1 -= arr[0][i]\n\t\tmx = min(mx, max(sum1, sum2))\n\t\tsum2 += arr[1][i]\n\tprint(mx)\n", "def int_input():\n\ta = int(input())\n\treturn a\n\ndef int_list_input():\n\ta = list(map(int, input().split()))\n\treturn a\n\ndef solve():\n\tn = int_input()\n\ta = int_list_input()\n\tb = int_list_input()\n\ta_s = [0 for _ in range(n)]\n\tb_s = [0 for _ in range(n)]\n\ta_s[-1] = a[-1]\n\tfor i in range(n - 2, -1, -1):\n\t\ta_s[i] = a_s[i + 1] + a[i]\n\tb_s[0] = b[0]\n\tfor i in range(1, n):\n\t\tb_s[i] = b_s[i - 1] + b[i]\n\tans = float('inf')\n\tfor i in range(n):\n\t\tans = min(ans, max(a_s[i] - a[i], b_s[i] - b[i]))\n\tprint(ans)\nfor _ in range(int(input())):\n\tsolve()\n", "for gg in range(int(input())):\n\tm = int(input())\n\ta1 = list(map(int, input().split()))\n\ta2 = list(map(int, input().split()))\n\tif m == 1:\n\t\tprint(0)\n\t\tcontinue\n\telse:\n\t\ts1 = 0\n\t\tfor i in range(m):\n\t\t\ts1 += a1[i]\n\t\ts2 = 0\n\t\tm1 = s1\n\t\tfor i in range(m + 1):\n\t\t\tif i == 0:\n\t\t\t\ts2 = 0\n\t\t\t\ts1 -= a1[i]\n\t\t\telif i != m:\n\t\t\t\ts2 += a2[i - 1]\n\t\t\t\ts1 -= a1[i]\n\t\t\telse:\n\t\t\t\ts1 = 0\n\t\t\t\ts2 += a2[i - 1]\n\t\t\tif max(s1, s2) < m1:\n\t\t\t\tm1 = max(s1, s2)\n\t\tprint(m1)\n", "import sys\ninput = sys.stdin.readline\nfrom itertools import accumulate\nINF = 1 << 64\nt = int(input())\nfor _ in range(t):\n\tm = int(input())\n\ta1 = list(map(int, input().split()))\n\ta2 = list(map(int, input().split()))\n\taa1 = [0] + list(accumulate(a1))\n\taa2 = [0] + list(accumulate(a2))\n\tans = INF\n\tfor i in range(1, m + 1):\n\t\tans = min(ans, max(aa1[m] - aa1[i], aa2[i - 1]))\n\tprint(ans)\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nfrom collections import defaultdict\nfrom math import ceil, floor, sqrt, log2, gcd, pi\nfrom heapq import heappush, heappop\nfrom fractions import Fraction\nfrom bisect import bisect_left, bisect\nimport sys\nabc = 'abcdefghijklmnopqrstuvwxyz'\nABC = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'\nfor i in range(int(input())):\n\tn = int(input())\n\tr1 = list(map(int, input().split()))\n\tr2 = list(map(int, input().split()))\n\tfor i in range(n - 2, 0, -1):\n\t\tr1[i] += r1[i + 1]\n\tr1[0] = 0\n\tr2[-1] = 0\n\tfor i in range(1, n - 1):\n\t\tr2[i] += r2[i - 1]\n\tif n == 1:\n\t\tprint(0)\n\telif n == 2:\n\t\tprint(min(r1[-1], r2[0]))\n\telse:\n\t\tarr = []\n\t\tfor i in range(n):\n\t\t\tif i == 0:\n\t\t\t\tarr.append(r1[1])\n\t\t\telif i == n - 1:\n\t\t\t\tarr.append(r2[-2])\n\t\t\telse:\n\t\t\t\tarr.append(max(r1[i + 1], r2[i - 1]))\n\t\tarr.sort()\n\t\tprint(min(arr))\n", "def ii():\n\treturn int(input())\n\ndef si():\n\treturn input()\n\ndef mi():\n\treturn map(int, input().split())\n\ndef msi():\n\treturn map(str, input().split())\n\ndef li():\n\treturn list(mi())\nmod = 10 ** 9\nt = ii()\nfor _ in range(t):\n\tm = ii()\n\tr1 = li()\n\tr2 = li()\n\tpre1 = [0] * m\n\tpre2 = [0] * m\n\tsumm = sum(r1)\n\tfor i in range(m):\n\t\tpre1[i] = pre1[i - 1] + r1[i]\n\t\tpre2[i] = pre2[i - 1] + r2[i]\n\ttemp = 0\n\tans = 10 ** 10\n\tfor i in range(m):\n\t\ttemp = max((summ - pre1[i]) % mod, (pre2[i] - r2[i]) % mod)\n\t\tans = min(ans, temp) % mod\n\tprint(ans % mod)\n", "t = int(input())\nfor u in range(t):\n\tm = int(input())\n\ts1 = list(map(int, input().split()))\n\ts2 = list(map(int, input().split()))\n\tif m == 1:\n\t\tprint(0)\n\telse:\n\t\tpr1 = []\n\t\tsu1 = 0\n\t\tfor i in range(m):\n\t\t\tsu1 += s1[i]\n\t\t\tpr1.append(su1)\n\t\tpr2 = []\n\t\tsu2 = 0\n\t\tfor i in range(m):\n\t\t\tsu2 += s2[i]\n\t\t\tpr2.append(su2)\n\t\tmans = sum(s1) + sum(s2)\n\t\tfor i in range(m):\n\t\t\tif i == 0:\n\t\t\t\ttans = pr1[-1] - pr1[0]\n\t\t\telif i == m - 1:\n\t\t\t\ttans = pr2[m - 2]\n\t\t\telse:\n\t\t\t\ttans = max(pr2[i - 1], pr1[-1] - pr1[i])\n\t\t\tmans = min(tans, mans)\n\t\tprint(mans)\n", "for _ in range(int(input())):\n\tn = int(input())\n\ta = []\n\tfor i in range(2):\n\t\ta.append(list(map(int, input().split())))\n\tsum1 = sum(a[0])\n\tsum2 = 0\n\tans = 1000000007\n\tfor i in range(n):\n\t\tsum1 -= a[0][i]\n\t\tans = min(ans, max(sum1, sum2))\n\t\tsum2 += a[1][i]\n\tprint(ans)\n", "def coins(m, a, b):\n\tcabove = sum(a) - a[0]\n\tcbelow = 0\n\tprvc = sum(a) - a[0]\n\tresult = prvc\n\tfor i in range(1, m):\n\t\tcabove = cabove - a[i]\n\t\tcbelow = cbelow + b[i - 1]\n\t\tprvc = max(cbelow, cabove)\n\t\tresult = min(prvc, result)\n\treturn result\nx = int(input())\nm = []\nfor i in range(x):\n\ta = int(input())\n\tz = input()\n\tz1 = z.split(' ')\n\tz2 = [int(t) for t in z1]\n\ty = input()\n\ty1 = y.split(' ')\n\ty2 = [int(t) for t in y1]\n\tm.append((a, z2, y2))\nfor j in range(x):\n\tprint(coins(m[j][0], m[j][1], m[j][2]))\n", "for _ in range(int(input())):\n\tn = int(input())\n\tlis1 = list(map(int, input().split()))\n\tlis2 = list(map(int, input().split()))\n\tsum1 = sum(lis1) - lis1[0]\n\tsum2 = 0\n\tif n == 1:\n\t\tprint(0)\n\t\tcontinue\n\tmini = 1000000007\n\tfor i in range(n - 1):\n\t\tsums = [sum1, sum2]\n\t\tif max(sums) < mini:\n\t\t\tmini = max(sums)\n\t\tsum2 += lis2[i]\n\t\tsum1 -= lis1[i + 1]\n\t\tsums = [sum1, sum2]\n\tif max(sums) < mini:\n\t\tmini = max(sums)\n\tif mini == 1000000007:\n\t\tprint(0)\n\telse:\n\t\tprint(mini)\n", "def solve(A, B, n):\n\tpref = [0]\n\tfor it in B:\n\t\tpref.append(pref[-1] + it)\n\tsuff = [0] * n\n\tcur = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tsuff[i] = cur\n\t\tcur += A[i]\n\tans = float('inf')\n\tfor i in range(n):\n\t\tmn = max(pref[i], suff[i])\n\t\tans = min(ans, mn)\n\treturn ans\nfor case in range(int(input())):\n\tn = int(input())\n\tA = list(map(int, input().split()))\n\tB = list(map(int, input().split()))\n\tans = solve(A, B, n)\n\tprint(ans)\n", "from decimal import *\nimport sys\ninput = sys.stdin.buffer.readline\nt = int(input())\nfor _ in range(t):\n\tn = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\t(x, y) = (0, n - 1)\n\t(a1, a2) = (0, 0)\n\twhile x != y:\n\t\tif a1 + b[x] <= a2 + a[y]:\n\t\t\ta1 += b[x]\n\t\t\tx += 1\n\t\telse:\n\t\t\ta2 += a[y]\n\t\t\ty -= 1\n\tprint(max(a1, a2))\n", "test = int(input())\nfor i in range(test):\n\tm = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\te = []\n\tc = sum(a)\n\td = 0\n\tfor j in range(m):\n\t\tif j == 0:\n\t\t\tc = c - a[j]\n\t\telse:\n\t\t\tc = c - a[j]\n\t\t\td = d + b[j - 1]\n\t\te.append(max(c, d))\n\tprint(min(e))\n", "import math\nt = int(input())\nwhile t:\n\tm = int(input())\n\tfinal = math.inf\n\tarray_1 = list(map(int, input().split()))\n\tarray_2 = list(map(int, input().split()))\n\tmi = math.inf\n\ta_sum = sum(array_1)\n\ta = 0\n\tb_sum = sum(array_2)\n\tb = b_sum\n\tfor i in range(m):\n\t\ta += array_1[i]\n\t\tif max(a_sum - a, b_sum - b) <= final:\n\t\t\tfinal = max(a_sum - a, b_sum - b)\n\t\tb -= array_2[i]\n\tprint(final)\n\tt -= 1\n", "for _ in range(int(input())):\n\tn = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tans = 0\n\tpref = [0] * n\n\tpref2 = [0] * n\n\tpref[0] = a[0]\n\tpref2[0] = b[0]\n\tfor i in range(1, n):\n\t\tpref[i] = pref[i - 1] + a[i]\n\t\tpref2[i] = pref2[i - 1] + b[i]\n\tpref2.append(0)\n\tm = 100000000000000\n\tfor i in range(n):\n\t\tx = max(pref[-1] - pref[i], pref2[i - 1])\n\t\tm = min(m, x)\n\tif n == 1:\n\t\tprint(0)\n\telse:\n\t\tprint(m)\n", "from collections import defaultdict as dd\nimport math\nimport sys\ninput = sys.stdin.readline\n\ndef nn():\n\treturn int(input())\n\ndef li():\n\treturn list(input())\n\ndef mi():\n\treturn map(int, input().split())\n\ndef lm():\n\treturn list(map(int, input().split()))\n\ndef solve():\n\tm = nn()\n\tr1 = lm()\n\tr2 = lm()\n\tbest = sum(r1) + sum(r2)\n\tabove = sum(r1) - r1[0]\n\tbelow = 0\n\tcur = max(above, below)\n\tbest = min(cur, best)\n\tfor i in range(m - 1):\n\t\tbelow += r2[i]\n\t\tabove -= r1[i + 1]\n\t\tcur = max(above, below)\n\t\tbest = min(cur, best)\n\tprint(best)\nq = nn()\nfor _ in range(q):\n\tsolve()\n", "import sys\nimport math\nimport heapq\nfrom collections import defaultdict as dd\nfrom collections import OrderedDict as od\nfrom collections import deque\nfrom itertools import permutations as pp\nfrom itertools import combinations as cc\nfrom sys import stdin\nfrom functools import cmp_to_key\nfrom functools import lru_cache\nfrom bisect import bisect_left as bs_l\nfrom bisect import bisect_right as bs_r\ninput = sys.stdin.readline\nmod = 10 ** 9 + 7\nsys.setrecursionlimit(10 ** 5)\nT = int(input())\nfor _ in range(T):\n\tn = int(input())\n\tarr = list(map(int, input().split()))\n\tbrr = list(map(int, input().split()))\n\t(asuf, bpref) = ([0] * (n + 1), [0] * (n + 1))\n\tfor i in range(1, n + 1):\n\t\tasuf[i] = asuf[i - 1] + arr[n - i]\n\t\tbpref[i] = bpref[i - 1] + brr[i - 1]\n\tasuf = asuf[::-1]\n\tans = 10 ** 9\n\tfor i in range(n):\n\t\taa = asuf[i + 1]\n\t\tbb = bpref[i]\n\t\tans = min(ans, max(aa, bb))\n\tprint(ans)\n", "def accumulate2(a):\n\timport itertools\n\treturn tuple(itertools.chain((0,), itertools.accumulate(a)))[:-1]\nfor _ in range(int(input())):\n\tm = int(input())\n\ta1sums = accumulate2(tuple(map(int, input().split()))[::-1])[::-1]\n\ta2sums = accumulate2(map(int, input().split()))\n\tprint(min(map(max, zip(a1sums, a2sums))))\n", "def naiveSolve():\n\treturn\n\ndef solve():\n\treturn\n\ndef main():\n\tt = int(input())\n\tallans = []\n\tfor _ in range(t):\n\t\tn = int(input())\n\t\ta1 = readIntArr()\n\t\ta2 = readIntArr()\n\t\tp1 = a1.copy()\n\t\tp2 = a2.copy()\n\t\tfor i in range(1, n):\n\t\t\tp1[i] += p1[i - 1]\n\t\t\tp2[i] += p2[i - 1]\n\n\t\tdef q(p, l, r):\n\t\t\tif r < 0:\n\t\t\t\treturn 0\n\t\t\tif l >= n:\n\t\t\t\treturn 0\n\t\t\tif l == 0:\n\t\t\t\treturn p[r]\n\t\t\treturn p[r] - p[l - 1]\n\t\tans = inf\n\t\tfor i in range(n):\n\t\t\tans = min(ans, max(q(p2, 0, i - 1), q(p1, i + 1, n - 1)))\n\t\tallans.append(ans)\n\tmultiLineArrayPrint(allans)\n\treturn\nimport sys\ninput = sys.stdin.buffer.readline\n\ndef oneLineArrayPrint(arr):\n\tprint(' '.join([str(x) for x in arr]))\n\ndef multiLineArrayPrint(arr):\n\tprint('\\n'.join([str(x) for x in arr]))\n\ndef multiLineArrayOfArraysPrint(arr):\n\tprint('\\n'.join([' '.join([str(x) for x in y]) for y in arr]))\n\ndef readIntArr():\n\treturn [int(x) for x in input().split()]\n\ndef makeArr(defaultValFactory, dimensionArr):\n\tdv = defaultValFactory\n\tda = dimensionArr\n\tif len(da) == 1:\n\t\treturn [dv() for _ in range(da[0])]\n\telse:\n\t\treturn [makeArr(dv, da[1:]) for _ in range(da[0])]\n\ndef queryInteractive(x):\n\tprint('{}'.format(x))\n\tsys.stdout.flush()\n\treturn int(input())\n\ndef answerInteractive(ans):\n\tprint('! {}'.format(ans))\n\tsys.stdout.flush()\ninf = float('inf')\nMOD = 998244353\nfrom math import gcd, floor, ceil\nfor _abc in range(1):\n\tmain()\n", "for t in range(int(input())):\n\tm = int(input())\n\ts1 = list(map(int, input().split()))\n\ts2 = list(map(int, input().split()))\n\tshag1 = m - 1\n\tshag2 = 0\n\tgrivna1 = 0\n\tgrivna2 = 0\n\twhile shag1 != shag2:\n\t\tif grivna1 + s1[shag1] < grivna2 + s2[shag2]:\n\t\t\tgrivna1 += s1[shag1]\n\t\t\tshag1 -= 1\n\t\telse:\n\t\t\tgrivna2 += s2[shag2]\n\t\t\tshag2 += 1\n\tprint(max(grivna1, grivna2))\n", "T = int(input())\nout = []\nfor t in range(T):\n\tm = int(input())\n\ta1 = [int(x) for x in input().split()]\n\ta2 = [int(x) for x in input().split()]\n\t(pre1, pre2) = ([a1[0]], [a2[0]])\n\tif m == 1:\n\t\tout.append(0)\n\t\tcontinue\n\tsuf1 = [a1[-1]]\n\tfor i in range(1, m):\n\t\tpre2.append(pre2[-1] + a2[i])\n\tfor i in range(m - 2, -1, -1):\n\t\tsuf1.append(suf1[-1] + a1[i])\n\tsuf1 = suf1[::-1]\n\tbob = float('inf')\n\topt1 = 0\n\tfor i in range(m):\n\t\tif i < m - 1 and i > 0:\n\t\t\tans = max(suf1[i + 1], pre2[i - 1])\n\t\telif i < m - 1:\n\t\t\tans = suf1[i + 1]\n\t\telse:\n\t\t\tans = pre2[i - 1]\n\t\tif ans < bob:\n\t\t\topt1 = i\n\t\t\tbob = ans\n\tout.append(bob)\nfor e in out:\n\tprint(e)\n", "for _ in range(int(input())):\n\tn = int(input())\n\ta = []\n\tfor _ in range(2):\n\t\ta.append(list(map(int, input().split())))\n\tl = []\n\tfor i in range(2):\n\t\ts = [0] * (n + 1)\n\t\tfor j in range(n):\n\t\t\ts[j + 1] = s[j] + a[i][j]\n\t\tl.append(s)\n\t\tans = float('inf')\n\tfor i in range(n):\n\t\tb = max(l[0][-1] - l[0][i + 1], l[1][i])\n\t\tans = min(ans, b)\n\tprint(ans)\n", "t = int(input())\nwhile t:\n\tt -= 1\n\tm = int(input())\n\ta = []\n\tfor i in range(2):\n\t\ta.append(list(map(int, input().split())))\n\tr = sum(a[0][1:m])\n\tn = 0\n\tk = 0\n\twhile k + 1 < m and r >= n:\n\t\tk += 1\n\t\tr -= a[0][k]\n\t\tn += a[1][k - 1]\n\tprint(min(n, r + a[0][k]))\n", "import sys\nint1 = lambda x: int(x) - 1\np2D = lambda x: print(*x, sep='\\n')\n\ndef II():\n\treturn int(sys.stdin.readline())\n\ndef LI():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef LLI(rows_number):\n\treturn [LI() for _ in range(rows_number)]\n\ndef LI1():\n\treturn list(map(int1, sys.stdin.readline().split()))\n\ndef LLI1(rows_number):\n\treturn [LI1() for _ in range(rows_number)]\n\ndef SI():\n\treturn sys.stdin.readline().rstrip()\ninf = 10 ** 16\nmd = 10 ** 9 + 7\n\ndef tocs(aa):\n\tres = [0]\n\tfor a in aa:\n\t\tres.append(res[-1] + a)\n\treturn res\n\ndef solve():\n\tn = II()\n\taa = LI()\n\tbb = LI()\n\tll = tocs(aa[::-1])\n\trr = tocs(bb)\n\tans = inf\n\tfor c in range(n):\n\t\tcur = max(ll[c], rr[n - 1 - c])\n\t\tif cur < ans:\n\t\t\tans = cur\n\tprint(ans)\nfor testcase in range(II()):\n\tsolve()\n", "from sys import stdin\ninput = stdin.readline\nrn = lambda : int(input())\nrns = lambda : map(int, input().split())\nrl = lambda : list(map(int, input().split()))\nrs = lambda : input().strip()\nYN = lambda x: print('YES') if x else print('NO')\nmod = 10 ** 9 + 7\nfrom itertools import accumulate\nfor _ in range(rn()):\n\tn = rn()\n\ttop = rl()\n\tbottom = rl()\n\tif n == 1:\n\t\tprint(0)\n\telse:\n\t\ttop = list(accumulate(top[::-1]))[::-1]\n\t\tbottom = list(accumulate(bottom))\n\t\tans = float('inf')\n\t\tfor i in range(1, n):\n\t\t\tif i == 1:\n\t\t\t\tans = min(ans, top[i])\n\t\t\telse:\n\t\t\t\tans = min(ans, max(top[i], bottom[i - 2]))\n\t\tans = min(ans, bottom[-2])\n\t\tprint(ans)\n", "T = int(input())\nfor t in range(T):\n\tm = int(input())\n\ta = [int(i) for i in input().split()]\n\tb = [int(i) for i in input().split()]\n\tA = [a, b]\n\tsufsumA = [0 for i in range(m)]\n\tsufsumB = [0 for i in range(m)]\n\tprefsumA = [0 for i in range(m)]\n\tprefsumB = [0 for i in range(m)]\n\tfor i in range(m - 1, -1, -1):\n\t\tif i == m - 1:\n\t\t\tsufsumA[i] = 0\n\t\t\tsufsumB[i] = A[1][i]\n\t\telse:\n\t\t\tsufsumA[i] = sufsumA[i + 1] + A[0][i + 1]\n\t\t\tsufsumB[i] = sufsumB[i + 1] + A[1][i]\n\tfor i in range(m):\n\t\tif i == 0:\n\t\t\tprefsumB[i] = 0\n\t\t\tprefsumA[i] = A[0][i]\n\t\telse:\n\t\t\tprefsumB[i] = prefsumB[i - 1] + A[1][i - 1]\n\t\t\tprefsumA[i] = prefsumA[i - 1] + A[0][i]\n\tans = 0\n\tbestalice = 0\n\tbestbob = 100000000000\n\tscoreofalice = 0\n\tscoreofbob = bestbob\n\tfor i in range(m):\n\t\tscoreofalice = prefsumA[i] + sufsumB[i]\n\t\tscoreofbob = max(prefsumB[i], sufsumA[i])\n\t\tif scoreofbob < bestbob:\n\t\t\tbestbob = scoreofbob\n\t\t\tans = bestbob\n\tprint(ans)\n", "def solve(m, mat):\n\tans = 1e+18\n\ttopsum = sum(mat[0])\n\tbotsum = 0\n\tfor i in range(m):\n\t\tif i > 0:\n\t\t\tbotsum += mat[1][i - 1]\n\t\ttopsum -= mat[0][i]\n\t\tans = min(ans, max(topsum, botsum))\n\treturn ans\nfor t in range(int(input())):\n\tm = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tprint(solve(m, [a, b]))\n", "def main():\n\tfor P in range(int(input())):\n\t\tiloL = int(input())\n\t\tlistG = list(map(int, input().split()))\n\t\tlistD = list(map(int, input().split()))\n\t\t(sumD, sumG) = (0, sum(listG) - listG[0])\n\t\twyn = sumG\n\t\tfor i in range(1, iloL):\n\t\t\tsumG -= listG[i]\n\t\t\tsumD += listD[i - 1]\n\t\t\twyn = min(wyn, max(sumG, sumD))\n\t\tprint(wyn)\nmain()\n", "def solution(m, row1: list, row2: list) -> int:\n\tif m == 1:\n\t\treturn 0\n\trow1[0] = 0\n\trow2[-1] = 0\n\ta = []\n\tb = []\n\tsm1 = 0\n\tsm2 = 0\n\tfor (c1, c2) in zip(row1, row2):\n\t\tsm1 += c1\n\t\tsm2 += c2\n\t\ta.append(sm1)\n\t\tb.append(sm2)\n\tmn = min(a[-1] - a[0], b[m - 2])\n\tfor i in range(1, m - 1):\n\t\tcurrent = max(b[i - 1], a[m - 1] - a[i])\n\t\tif current < mn:\n\t\t\tmn = current\n\treturn mn\n\ndef main():\n\tfor _ in range(int(input())):\n\t\tm = int(input())\n\t\trow1 = list(map(int, input().split()))\n\t\trow2 = list(map(int, input().split()))\n\t\tprint(solution(m, row1, row2))\nmain()\n", "import sys\ninput = sys.stdin.readline\n\ndef solve():\n\tn = int(input())\n\ta = [list(map(int, input().strip().split())) for i in range(2)]\n\tpref0 = [a[0][0]]\n\tpref1 = [a[1][0]]\n\tfor i in range(1, n):\n\t\tpref0 += [pref0[-1] + a[0][i]]\n\t\tpref1 += [pref1[-1] + a[1][i]]\n\tpref0 = [0] + pref0\n\tpref1 = [0] + pref1\n\tans = 10 ** 100\n\tfor i in range(n):\n\t\tans = min(ans, max(pref0[-1] - pref0[i + 1], pref1[i] - pref1[0]))\n\tprint(ans)\nfor _ in range(int(input())):\n\tsolve()\n", "t = int(input())\nfor _ in range(t):\n\tn = int(input())\n\ta = []\n\tfor _ in range(2):\n\t\ta.append(list(map(int, input().split())))\n\tans = float('inf')\n\t(sum1, sum2) = (0, 0)\n\tfor i in range(n):\n\t\tsum1 += a[0][i]\n\tfor i in range(n):\n\t\tsum1 -= a[0][i]\n\t\tans = min(ans, max(sum1, sum2))\n\t\tsum2 += a[1][i]\n\tprint(ans)\n", "t = int(input())\nfor _ in range(t):\n\tm = int(input())\n\ta = [list(map(int, input().split())) for i in range(2)]\n\tif m == 1:\n\t\tprint(0)\n\t\tcontinue\n\t(t_l, t_r) = (0, 0)\n\t(L, R) = (0, m - 1)\n\twhile L != R:\n\t\tif t_l <= t_r:\n\t\t\tt_l += a[1][L]\n\t\t\tL += 1\n\t\telse:\n\t\t\tt_r += a[0][R]\n\t\t\tR -= 1\n\tM = max(t_l, t_r)\n\tif L > 0:\n\t\tM = min(M, max(t_l - a[1][L - 1], t_r + a[0][R]))\n\tif R < m - 1:\n\t\tM = min(M, max(t_l + a[1][L], t_r - a[0][R + 1]))\n\tprint(M)\n", "import sys\ninput = sys.stdin.readline\nt = int(input())\nfor i in range(t):\n\tm = int(input())\n\tc = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\td = [0 for i in range(m)]\n\te = [0 for i in range(m)]\n\td[0] = b[0]\n\te[m - 1] = c[m - 1]\n\tfor i in range(1, m):\n\t\td[i] = d[i - 1] + b[i]\n\tfor i in range(m - 2, -1, -1):\n\t\te[i] = e[i + 1] + c[i]\n\tan = min(sum(c[1:m]), sum(b[:m - 1]))\n\tfor i in range(1, m - 1):\n\t\tan = min(an, max(d[i - 1], e[i + 1]))\n\tprint(an)\n", "import sys\nread = sys.stdin.buffer.read\nreadline = sys.stdin.buffer.readline\ninput = lambda : sys.stdin.readline().rstrip()\nimport bisect, string, math, time, functools, random, fractions\nfrom heapq import heappush, heappop, heapify\nfrom collections import deque, defaultdict, Counter\nfrom itertools import permutations, combinations, groupby\nrep = range\nR = range\n\ndef I():\n\treturn int(input())\n\ndef LI():\n\treturn [int(i) for i in input().split()]\n\ndef LI_():\n\treturn [int(i) - 1 for i in input().split()]\n\ndef S_():\n\treturn input()\n\ndef IS():\n\treturn input().split()\n\ndef LS():\n\treturn [i for i in input().split()]\n\ndef NI(n):\n\treturn [int(input()) for i in range(n)]\n\ndef NI_(n):\n\treturn [int(input()) - 1 for i in range(n)]\n\ndef NLI(n):\n\treturn [[int(i) for i in input().split()] for i in range(n)]\n\ndef NLI_(n):\n\treturn [[int(i) - 1 for i in input().split()] for i in range(n)]\n\ndef StoLI():\n\treturn [ord(i) - 97 for i in input()]\n\ndef ItoS(n):\n\treturn chr(n + 97)\n\ndef LtoS(ls):\n\treturn ''.join([chr(i + 97) for i in ls])\n\ndef RLI(n=8, a=1, b=10):\n\treturn [random.randint(a, b) for i in range(n)]\n\ndef RI(a=1, b=10):\n\treturn random.randint(a, b)\n\ndef INP():\n\tN = 9\n\tn = random.randint(1, N)\n\tA = [random.randint(1, n) for i in range(m)]\n\treturn (n, A)\n\ndef Rtest(T):\n\t(case, err) = (0, 0)\n\tfor i in range(T):\n\t\tinp = INP()\n\t\ta1 = naive(*inp)\n\t\ta2 = solve(*inp)\n\t\tif a1 != a2:\n\t\t\tprint(inp)\n\t\t\tprint('naive', a1)\n\t\t\tprint('solve', a2)\n\t\t\terr += 1\n\t\tcase += 1\n\tprint('Tested', case, 'case with', err, 'errors')\n\ndef GI(V, E, ls=None, Directed=False, index=1):\n\torg_inp = []\n\tg = [[] for i in range(V)]\n\tFromStdin = True if ls == None else False\n\tfor i in range(E):\n\t\tif FromStdin:\n\t\t\tinp = LI()\n\t\t\torg_inp.append(inp)\n\t\telse:\n\t\t\tinp = ls[i]\n\t\tif len(inp) == 2:\n\t\t\t(a, b) = inp\n\t\t\tc = 1\n\t\telse:\n\t\t\t(a, b, c) = inp\n\t\tif index == 1:\n\t\t\ta -= 1\n\t\t\tb -= 1\n\t\taa = (a, c)\n\t\tbb = (b, c)\n\t\tg[a].append(bb)\n\t\tif not Directed:\n\t\t\tg[b].append(aa)\n\treturn (g, org_inp)\n\ndef GGI(h, w, search=None, replacement_of_found='.', mp_def={'#': 1, '.': 0}, boundary=1):\n\tmp = [boundary] * (w + 2)\n\tfound = {}\n\tfor i in R(h):\n\t\ts = input()\n\t\tfor char in search:\n\t\t\tif char in s:\n\t\t\t\tfound[char] = (i + 1) * (w + 2) + s.index(char) + 1\n\t\t\t\tmp_def[char] = mp_def[replacement_of_found]\n\t\tmp += [boundary] + [mp_def[j] for j in s] + [boundary]\n\tmp += [boundary] * (w + 2)\n\treturn (h + 2, w + 2, mp, found)\n\ndef TI(n):\n\treturn GI(n, n - 1)\n\ndef accum(ls):\n\trt = [0]\n\tfor i in ls:\n\t\trt += [rt[-1] + i]\n\treturn rt\n\ndef bit_combination(n, base=2):\n\trt = []\n\tfor tb in R(base ** n):\n\t\ts = [tb // base ** bt % base for bt in R(n)]\n\t\trt += [s]\n\treturn rt\n\ndef gcd(x, y):\n\tif y == 0:\n\t\treturn x\n\tif x % y == 0:\n\t\treturn y\n\twhile x % y != 0:\n\t\t(x, y) = (y, x % y)\n\treturn y\n\ndef YN(x):\n\tprint(['NO', 'YES'][x])\n\ndef Yn(x):\n\tprint(['No', 'Yes'][x])\n\ndef show(*inp, end='\\n'):\n\tif show_flg:\n\t\tprint(*inp, end=end)\nmo = 10 ** 9 + 7\ninf = 1 << 63\nFourNb = [(-1, 0), (1, 0), (0, 1), (0, -1)]\nEightNb = [(-1, 0), (1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]\ncompas = dict(zip('WENS', FourNb))\ncursol = dict(zip('LRUD', FourNb))\nalp = [chr(ord('a') + i) for i in range(26)]\nshow_flg = False\nshow_flg = True\n\ndef primeFactor(N):\n\t(i, n) = (2, N)\n\tret = {}\n\t(d, sq) = (2, 99)\n\twhile i <= sq:\n\t\tk = 0\n\t\twhile n % i == 0:\n\t\t\t(n, k, ret[i]) = (n // i, k + 1, k + 1)\n\t\tif k > 0 or i == 97:\n\t\t\tsq = int(n ** (1 / 2) + 0.5)\n\t\tif i < 4:\n\t\t\ti = i * 2 - 1\n\t\telse:\n\t\t\t(i, d) = (i + d, d ^ 6)\n\tif n > 1:\n\t\tret[n] = 1\n\treturn ret\n\ndef divisors(n):\n\tdiv = [1]\n\tfor (i, j) in primeFactor(n).items():\n\t\tdiv = [i ** k * d for d in div for k in range(j + 1)]\n\treturn div\n\ndef sieve(x):\n\ts = [i for i in range(x + 1)]\n\tp = 2\n\twhile p * p <= x:\n\t\tif s[p] == p:\n\t\t\tfor q in range(2 * p, x + 1, p):\n\t\t\t\tif s[q] == q:\n\t\t\t\t\ts[q] = p\n\t\tp += 1\n\treturn s\n\ndef PrimeNumSet(N):\n\tM = int(N ** 0.5)\n\tseachList = [i for i in range(2, N + 1)]\n\tprimes = []\n\twhile seachList:\n\t\tif seachList[0] > M:\n\t\t\tbreak\n\t\tprimes.append(seachList[0])\n\t\ttmp = seachList[0]\n\t\tseachList = [i for i in seachList if i % tmp != 0]\n\treturn primes + seachList\n\ndef LCM(b, mo=10 ** 9 + 7):\n\tprs = PrimeNumSet(max(b))\n\tM = dict(zip(prs, [0] * len(prs)))\n\tfor i in b:\n\t\tdc = primeFactor(i)\n\t\tfor (j, k) in dc.items():\n\t\t\tM[j] = max(M[j], k)\n\tr = 1\n\tfor (j, k) in M.items():\n\t\tif k != 0:\n\t\t\tr *= pow(j, k, mo)\n\t\t\tr %= mo\n\treturn r\n\ndef extgcd(x, y):\n\tif y == 0:\n\t\treturn (1, 0)\n\t(r0, r1, s0, s1) = (x, y, 1, 0)\n\twhile r1 != 0:\n\t\t(r0, r1, s0, s1) = (r1, r0 % r1, s1, s0 - r0 // r1 * s1)\n\treturn (s0, (r0 - s0 * x) // y, x * s0 + y * (r0 - s0 * x) // y)\n\ndef crt(rems, mods):\n\tn = len(rems)\n\tif n != len(mods):\n\t\treturn NotImplemented\n\t(x, d) = (0, 1)\n\tfor (r, m) in zip(rems, mods):\n\t\t(a, b, g) = extgcd(d, m)\n\t\t(x, d) = ((m * b * x + d * a * r) // g, d * (m // g))\n\t\tx %= d\n\tfor (r, m) in zip(rems, mods):\n\t\tif r != x % m:\n\t\t\treturn (-1, d)\n\treturn (x, d)\n\ndef intsqrt(x):\n\tif x < 0:\n\t\treturn NotImplemented\n\trt = int(x ** 0.5) - 1\n\twhile (rt + 1) ** 2 <= x:\n\t\trt += 1\n\treturn rt\nans = 0\nfor _ in range(I()):\n\tn = I()\n\ta = LI()\n\tb = LI()\n\tans = d = sum(b[:n - 1])\n\tu = 0\n\tfor i in range(n - 2, -1, -1):\n\t\td -= b[i]\n\t\tu += a[i + 1]\n\t\tans = min(ans, max(u, d))\n\tprint(ans)\n", "for _ in range(int(input())):\n\tm = int(input())\n\tfield = []\n\tfor i in range(2):\n\t\tfield.append(list(map(int, input().split())))\n\tup = [0 for i in range(m)]\n\ta = 0\n\tfor i in range(m - 1):\n\t\ta += field[0][m - i - 1]\n\t\tup[m - i - 2] = a\n\tdown = [0 for i in range(m)]\n\ta = 0\n\tfor i in range(m - 1):\n\t\ta += field[1][i]\n\t\tdown[i + 1] = a\n\tans = 10 ** 9\n\tfor i in range(m):\n\t\tans = min(ans, max(down[i], up[i]))\n\tprint(ans)\n", "t = int(input())\nfor _ in range(t):\n\tm = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\ts = sum(a)\n\tz = 0\n\tza = 10 ** 10\n\tfor j in range(m):\n\t\tza = min(za, max(s - a[j], z))\n\t\ts -= a[j]\n\t\tz += b[j]\n\tprint(za)\n", "for t in range(int(input())):\n\tm = int(input())\n\ta2 = list(map(int, input().split()))\n\ta1 = list(map(int, input().split()))\n\tp = [0]\n\ts = [sum(a2)]\n\tfor v in a1:\n\t\tp.append(p[-1] + v)\n\tfor v in a2:\n\t\ts.append(s[-1] - v)\n\tans = 10 ** 18\n\tfor i in range(m):\n\t\tans = min(ans, max(p[i], s[i + 1]))\n\tprint(ans)\n", "t = int(input())\nwhile t:\n\tn = int(input())\n\tres = []\n\tres.append(list(map(int, input().split())))\n\tres.append(list(map(int, input().split())))\n\tres1 = []\n\tsumm = 0\n\tres1.append(0)\n\tfor i in range(n - 1, 0, -1):\n\t\tsumm += res[0][i]\n\t\tres1.append(summ)\n\tres1 = res1[::-1]\n\tsumm = 0\n\tres2 = []\n\tres2.append(0)\n\tfor i in range(n - 1):\n\t\tsumm += res[1][i]\n\t\tres2.append(summ)\n\tminn = max(res1[0], res2[0])\n\tfor i in range(1, n):\n\t\tif max(res1[i], res2[i]) < minn:\n\t\t\tminn = max(res1[i], res2[i])\n\tprint(minn)\n\tt -= 1\n", "n = int(input())\nwhile n > 0:\n\tans = []\n\tn -= 1\n\tm = int(input())\n\tfor i in range(2):\n\t\ts = [int(i) for i in input().split()]\n\t\tans.append(s)\n\tif m == 1:\n\t\tprint(0)\n\telse:\n\t\tdp = [0] * m\n\t\tdp[0] = sum(ans[0][1:])\n\t\ta = 0\n\t\tb = sum(ans[0][1:])\n\t\tfor i in range(1, m):\n\t\t\ta += ans[1][i - 1]\n\t\t\tb -= ans[0][i]\n\t\t\tdp[i] = max(b, a)\n\t\tprint(min(dp))\n", "t = int(input())\nfor task in range(t):\n\tm = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tres = sum(a) - a[0]\n\tsumA = res\n\tsumB = 0\n\tfor i in range(1, m):\n\t\tsumA -= a[i]\n\t\tsumB += b[i - 1]\n\t\ttmp = max(sumA, sumB)\n\t\tif tmp < res:\n\t\t\tres = tmp\n\tprint(res)\n", "import sys\nimport math\nfrom math import *\nimport builtins\nimport collections\nimport bisect\nimport os\nfrom io import BytesIO, IOBase\n\ndef print(x, end='\\n'):\n\tsys.stdout.write(str(x) + end)\n\ndef get_int():\n\treturn int(input())\n\ndef get_list_ints():\n\treturn list(map(int, input().split()))\n\ndef get_char_list():\n\ts = input()\n\treturn list(s[:len(s) - 1])\n\ndef get_tuple_ints():\n\treturn tuple(map(int, input().split()))\n\ndef print_iterable(p):\n\tprint(' '.join(map(str, p)))\n\ndef CountFrequency(arr):\n\treturn collections.Counter(arr)\n\ndef reverse(s):\n\tl = len(s)\n\tfor i in range(l // 2):\n\t\t(s[i], s[l - i - 1]) = (s[l - i - 1], s[i])\n\treturn s\n\ndef binary_search(arr, x):\n\tlow = 0\n\thigh = len(arr) - 1\n\tmid = 0\n\twhile low <= high:\n\t\tmid = (high + low) // 2\n\t\tif arr[mid] < x:\n\t\t\tlow = mid + 1\n\t\telif arr[mid] > x:\n\t\t\thigh = mid - 1\n\t\telse:\n\t\t\treturn mid\n\treturn high\n\ndef lower_bound(arr, x):\n\treturn bisect.bisect_left(arr, x, lo=0, hi=len(arr))\n\ndef upper_bound(arr, x):\n\treturn bisect.bisect_right(arr, x, lo=0, hi=len(arr))\n\ndef position(x):\n\treturn ord(x) - ord('a') + 1\n\ndef pow(a, n):\n\tif n == 0:\n\t\treturn 1\n\telif n % 2 == 0:\n\t\treturn pow(a, n // 2) % const * (pow(a, n // 2) % const) % const\n\telse:\n\t\treturn pow(a, n // 2) % const * (pow(a, n // 2) % const) * (a % const) % const\nR = 3\nC = 3\n\ndef main():\n\tn = get_int()\n\tfor i in range(n):\n\t\tm = get_int()\n\t\trow1 = get_list_ints()\n\t\trow2 = get_list_ints()\n\t\tslist = [0]\n\t\tfor i in range(m - 1):\n\t\t\tslist.append(slist[-1] + row2[i])\n\t\tslist2 = [0]\n\t\tfor i in range(m - 1, 0, -1):\n\t\t\tslist2.append(slist2[-1] + row1[i])\n\t\tslist2 = reverse(slist2)\n\t\tanslist = []\n\t\tfor i in range(m):\n\t\t\tanslist.append(max(slist[i], slist2[i]))\n\t\tprint(min(anslist))\n\tpass\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nmain()\n", "import sys\ninput = sys.stdin.readline\n\ndef dub(i, a1, a2):\n\tm = len(a1)\n\tif i == 0:\n\t\treturn a1[m - 1] - a1[0]\n\treturn max(a2[i - 1], a1[m - 1] - a1[i])\n\ndef solve():\n\tm = int(input())\n\ta1 = [int(x) for x in input().split()]\n\ta2 = [int(x) for x in input().split()]\n\tfor i in range(1, m):\n\t\ta1[i] += a1[i - 1]\n\tfor i in range(1, m):\n\t\ta2[i] += a2[i - 1]\n\tans = 1e+20\n\tfor i in range(m):\n\t\tans = min(ans, dub(i, a1, a2))\n\treturn ans\nt = int(input())\nfor _ in range(t):\n\tprint(solve())\n", "T = int(input())\nfor t in range(T):\n\tn = int(input())\n\tarr = [list(map(int, input().split())) for i in range(2)]\n\tupper_row = sum(arr[0])\n\tsuf = upper_row - arr[0][0]\n\tpre = 0\n\tmn = 10000000000000\n\tmn = min(max(pre, suf), mn)\n\tfor i in range(1, n):\n\t\tsuf -= arr[0][i]\n\t\tpre += arr[1][i - 1]\n\t\tans = max(suf, pre)\n\t\tmn = min(ans, mn)\n\tprint(mn)\n", "t = int(input())\nfor k in range(t):\n\tn = int(input())\n\tl = []\n\tfor i in range(2):\n\t\ttmp = list(map(int, input().split()))\n\t\tl.append(tmp)\n\tr1 = sum(l[0])\n\tr2 = sum(l[1])\n\tres = [r1 - l[0][0], r2 - l[1][n - 1]]\n\ta = r1 - l[0][0]\n\tb = 0\n\tfor i in range(n - 2):\n\t\ta -= l[0][i + 1]\n\t\tb += l[1][i]\n\t\tres.append(max(a, b))\n\tprint(min(res))\n", "from sys import stdin\ninput = stdin.buffer.readline\n\ndef func():\n\tpref_up = [mat[0][0]]\n\tpref_down = [mat[1][0]]\n\tfor i in range(1, m):\n\t\tpref_up.append(pref_up[-1] + mat[0][i])\n\t\tpref_down.append(pref_down[-1] + mat[1][i])\n\trem = 10000000000.0\n\tfor i in range(m):\n\t\trem = min(rem, max(pref_up[-1] - pref_up[i], pref_down[i] - mat[1][i]))\n\tprint(rem)\nfor _ in range(int(input())):\n\tm = int(input())\n\tmat = list()\n\tmat.append(list(map(int, input().split())))\n\tmat.append(list(map(int, input().split())))\n\tfunc()\n", "from math import *\nt = int(input())\nfor _ in range(t):\n\tn = int(input())\n\ta = []\n\ta.append(list(map(int, input().split())))\n\ta.append(list(map(int, input().split())))\n\tpre = [a[0][-1]]\n\tfor i in range(n - 2, -1, -1):\n\t\tpre.append(pre[-1] + a[0][i])\n\tpre = pre[::-1]\n\tsuf = [a[1][0]]\n\tfor i in range(1, n):\n\t\tsuf.append(suf[-1] + a[1][i])\n\tans = 10 ** 20\n\tif n == 1:\n\t\tprint(0)\n\t\tcontinue\n\tfor i in range(n):\n\t\tif i == 0:\n\t\t\tans = min(ans, pre[i + 1])\n\t\telif i == n - 1:\n\t\t\tans = min(ans, suf[i - 1])\n\t\telse:\n\t\t\tans = min(ans, max(pre[i + 1], suf[i - 1]))\n\tprint(ans)\n", "import heapq\nfrom collections import defaultdict, deque\nfrom itertools import accumulate\nfrom math import inf\nMOD = 10 ** 9 + 7\nt = int(input())\n\ndef solve():\n\tm = int(input())\n\tn = 2\n\tG = []\n\tfor _ in range(2):\n\t\trow = list(map(int, input().split()))\n\t\tG.append(row)\n\tpaths = [0] * m\n\tps_upper = list(accumulate(G[0]))\n\tps_lower = list(accumulate(G[1]))\n\tfor i in range(m):\n\t\tif i > 0:\n\t\t\tpaths[i] = max(ps_upper[m - 1] - ps_upper[i], ps_lower[max(0, i - 1)])\n\t\telse:\n\t\t\tpaths[i] = max(ps_upper[m - 1] - ps_upper[i], 0)\n\treturn min(paths)\nfor _ in range(t):\n\tsol = solve()\n\tprint(sol)\n", "def maxCoin(dp, total):\n\tmx = float('-inf')\n\tmn = float('inf')\n\tfor i in range(m):\n\t\tmx = max(mx, dp[0][i] + dp[1][i])\n\t\tmn = min(mn, max(total - dp[0][i], dp[1][0] - dp[1][i]))\n\treturn (mx, mn)\nt = int(input())\nfor _ in range(t):\n\tm = int(input())\n\tarr = []\n\tfor k in range(2):\n\t\tarr.append(list(map(int, input().split())))\n\tdp = [[0 for i in range(m)] for j in range(2)]\n\t(x, y) = (0, 0)\n\tfor i in range(m - 1, -1, -1):\n\t\ty += arr[0][m - i - 1]\n\t\tx += arr[1][i]\n\t\t(dp[0][m - i - 1], dp[1][i]) = (y, x)\n\ttotal = sum(arr[0])\n\t(mx, mn) = maxCoin(dp, total)\n\tprint(mn)\n", "import sys\np2D = lambda x: print(*x, sep='\\n')\n\ndef II():\n\treturn int(sys.stdin.buffer.readline())\n\ndef MI():\n\treturn map(int, sys.stdin.buffer.readline().split())\n\ndef LI():\n\treturn list(map(int, sys.stdin.buffer.readline().split()))\n\ndef LLI(rows_number):\n\treturn [LI() for _ in range(rows_number)]\n\ndef BI():\n\treturn sys.stdin.buffer.readline().rstrip()\n\ndef SI():\n\treturn sys.stdin.buffer.readline().rstrip().decode()\n\ndef li():\n\treturn [int(i) for i in input().split()]\n\ndef lli(rows):\n\treturn [li() for _ in range(rows)]\n\ndef si():\n\treturn input()\n\ndef ii():\n\treturn int(input())\n\ndef ins():\n\treturn input().split()\n\ndef solve():\n\tm = II()\n\ta = []\n\tfor i in range(2):\n\t\ta.append(LI())\n\tt1 = [0]\n\tt2 = [a[1][-1]]\n\tt3 = [0]\n\tfor i in range(m - 1):\n\t\tt1.append(t1[-1] + a[0][-1 - i])\n\tt1.reverse()\n\tfor i in range(m - 1):\n\t\tt3.append(t3[-1] + a[1][i])\n\tbs = 0\n\ttt = []\n\tfor i in range(m):\n\t\ttt.append(max(t3[i], t1[i]))\n\treturn min(tt) if len(tt) > 0 else 0\n\ndef main():\n\tfor _ in range(II()):\n\t\tsys.stdout.write(str(solve()) + '\\n')\nmain()\n", "t = int(input())\nfor _ in range(t):\n\tm = int(input())\n\ta = [list(map(int, input().split())) for _ in range(2)]\n\tr = [[0], [0]]\n\tfor i in range(2):\n\t\tfor j in range(m):\n\t\t\tr[i].append(r[i][j] + a[i][j])\n\tans = 10 ** 10\n\tfor i in range(m):\n\t\tans = min(ans, max(r[1][i], r[0][m] - r[0][i + 1]))\n\tprint(ans)\n", "sr = lambda : input()\nir = lambda : int(sr())\nlr = lambda : list(map(int, sr().split()))\ninf = 10 ** 18\nmod = 998244353\ntest = ir()\nfor t in range(test):\n\tm = ir()\n\ta1 = lr()\n\ta2 = lr()\n\taa1 = [0]\n\taa2 = [0]\n\tfor i in range(m):\n\t\taa1.append(aa1[-1] + a1[i])\n\t\taa2.append(aa2[-1] + a2[i])\n\tans = inf\n\tpre = 0\n\tfor i in range(m):\n\t\tuans = aa1[m] - aa1[i + 1]\n\t\tdans = aa2[i] - aa2[0]\n\t\tpre = max(uans, dans)\n\t\tans = min(ans, pre)\n\tprint(ans)\n", "import sys\nfrom itertools import accumulate\n\ndef I():\n\treturn int(sys.stdin.readline().rstrip())\n\ndef MI():\n\treturn map(int, sys.stdin.readline().rstrip().split())\n\ndef LI():\n\treturn list(map(int, sys.stdin.readline().rstrip().split()))\n\ndef LI2():\n\treturn list(map(int, sys.stdin.readline().rstrip()))\n\ndef S():\n\treturn sys.stdin.readline().rstrip()\n\ndef LS():\n\treturn list(sys.stdin.readline().rstrip().split())\n\ndef LS2():\n\treturn list(sys.stdin.readline().rstrip())\nt = I()\nfor _ in range(t):\n\tm = I()\n\tA = [LI() for _ in range(2)]\n\tSA0 = list(accumulate([0] + A[0]))\n\tSA1 = list(accumulate([0] + A[1]))\n\tans = 10 ** 18\n\tfor j in range(1, m + 1):\n\t\ta = max(SA0[-1] - SA0[j], SA1[j - 1])\n\t\tans = min(ans, a)\n\tprint(ans)\n", "for _ in range(int(input())):\n\tn = int(input())\n\tl1 = list(map(int, input().split()))\n\tl2 = list(map(int, input().split()))\n\tsm = sum(l1)\n\tld1 = [l1[0]]\n\tfor i in range(1, n):\n\t\tld1.append(ld1[-1] + l1[i])\n\tld1.append(0)\n\tld2 = [l2[0]]\n\tfor i in range(1, n):\n\t\tld2.append(ld2[-1] + l2[i])\n\tld2.insert(0, 0)\n\tmn = 1000000000\n\ti = 0\n\twhile i < n:\n\t\tmn = min(mn, max(sm - ld1[i], ld2[i]))\n\t\ti += 1\n\tprint(mn)\n", "def main():\n\tt = int(input())\n\tif t < 1 or t > 10000:\n\t\treturn\n\tfor _ in range(t):\n\t\tm = int(input())\n\t\tif m < 1 or m > 100000:\n\t\t\treturn\n\t\tr1 = list(map(int, input().split()))\n\t\tr2 = list(map(int, input().split()))\n\t\tdata = list()\n\t\tpref = 0\n\t\tsuff = sum(r1) - r1[0]\n\t\ta_min = suff + r1[0]\n\t\tfor i in range(m):\n\t\t\tn_min = max(pref, suff)\n\t\t\tif n_min < a_min:\n\t\t\t\ta_min = n_min\n\t\t\tpref += r2[i]\n\t\t\tif i + 1 == m:\n\t\t\t\tsuff = 0\n\t\t\telse:\n\t\t\t\tsuff -= r1[i + 1]\n\t\tprint(a_min)\nmain()\n", "t = int(input())\nwhile t > 0:\n\tt -= 1\n\tn = int(input())\n\ts = input().split()\n\ta = [int(x) for x in s]\n\ts = input().split()\n\tb = [int(x) for x in s]\n\tsu = 0\n\tsuma = []\n\tsumb = []\n\tfor x in a:\n\t\tsu += x\n\t\tsuma.append(su)\n\tans = su\n\tsu = 0\n\tfor x in b:\n\t\tsu += x\n\t\tsumb.append(su)\n\tans = ans + su + 10\n\tansIndex = 0\n\tansb = ans\n\tfor i in range(n):\n\t\ttempa = 0\n\t\ttempb = 0\n\t\tif i == 0:\n\t\t\ttempa = sumb[n - 1] + suma[0]\n\t\t\ttempb = suma[n - 1] - suma[0]\n\t\telif i == n - 1:\n\t\t\ttempa = suma[n - 1] + b[n - 1]\n\t\t\tif n > 1:\n\t\t\t\ttempb = sumb[n - 2]\n\t\telse:\n\t\t\ttempa = suma[i] + sumb[n - 1] - sumb[i - 1]\n\t\t\ttempb = max(sumb[i - 1], suma[n - 1] - suma[i])\n\t\tif tempb < ansb:\n\t\t\tansb = tempb\n\tprint(ansb)\n", "for _ in range(int(input())):\n\tm = int(input())\n\tls1 = list(map(int, input().split()))\n\tls2 = list(map(int, input().split()))\n\tif m == 1:\n\t\tprint(0)\n\telse:\n\t\tsumt = sum(ls1) + sum(ls2)\n\t\tfor i in range(1, m):\n\t\t\tls1[i] = ls1[i] + ls1[i - 1]\n\t\tfor i in range(m - 2, -1, -1):\n\t\t\tls2[i] = ls2[i] + ls2[i + 1]\n\t\trs = min(ls1[m - 1] - ls1[0], ls2[0] - ls2[m - 1])\n\t\tfor i in range(1, m - 1):\n\t\t\trs = min(rs, max(ls1[m - 1] - ls1[i], ls2[0] - ls2[i]))\n\t\tprint(rs)\n", "t = int(input())\nwhile t > 0:\n\tt -= 1\n\tn = int(input())\n\tstr1 = input().split()\n\tstr1 = [int(x) for x in str1]\n\tstr2 = input().split()\n\tstr2 = [int(x) for x in str2]\n\tqun1 = []\n\tqun2 = []\n\ttemp1 = 0\n\ttemp2 = 0\n\tfor j in range(0, n):\n\t\ttemp1 += str1[j]\n\t\tqun1.append(temp1)\n\t\ttemp2 += str2[j]\n\t\tqun2.append(temp2)\n\tans = qun1[n - 1] + qun2[n - 1]\n\tfor ii in range(n):\n\t\tif ii == n - 1:\n\t\t\tans1 = 0\n\t\telse:\n\t\t\tans1 = qun1[n - 1] - qun1[ii]\n\t\tif ii == 0:\n\t\t\tans2 = 0\n\t\telse:\n\t\t\tans2 = qun2[ii - 1]\n\t\tans3 = max(ans1, ans2)\n\t\tans = min(ans, ans3)\n\tprint(ans)\n", "for _ in range(int(input().strip())):\n\tcols = int(input().strip())\n\ta = list(map(int, input().strip().split()))\n\tb = list(map(int, input().strip().split()))\n\t(l, u, ans) = (0, sum(a), 1000000000.0)\n\tfor i in range(cols):\n\t\tu -= a[i]\n\t\tans = min(ans, max(u, l))\n\t\tl += b[i]\n\tprint(ans)\n", "ans = []\nfor _ in range(int(input())):\n\tn = int(input())\n\ta = [0] + list(map(int, input().split()))\n\tb = [0] + list(map(int, input().split()))\n\tfor i in range(1, n + 1):\n\t\ta[i] += a[i - 1]\n\t\tb[i] += b[i - 1]\n\tmn = 10 ** 10\n\tfor i in range(1, n + 1):\n\t\tcur = max(b[i - 1], a[-1] - a[i])\n\t\tmn = min(mn, cur)\n\tans.append(mn)\nprint('\\n'.join(map(str, ans)))\n", "t = int(input())\nfor _ in range(t):\n\tm = int(input())\n\trow1 = list(map(int, input().split()))\n\trow2 = list(map(int, input().split()))\n\ttopsum = sum(row1)\n\tbottomsum = 0\n\tanswer = float('inf')\n\tfor i in range(m):\n\t\ttopsum -= row1[i]\n\t\tanswer = min(answer, max(topsum, bottomsum))\n\t\tbottomsum += row2[i]\n\tprint(answer)\n", "for _ in range(int(input())):\n\tm = int(input())\n\tfield = tuple((tuple(map(int, input().split())), tuple(map(int, input().split()))))\n\t(a, b) = (sum(field[0][1:]), 0)\n\tfor (a_part, b_part) in zip(field[0][1:], field[1][:-1]):\n\t\tif max(a - a_part, b + b_part) > max(a, b):\n\t\t\tbreak\n\t\ta -= a_part\n\t\tb += b_part\n\tprint(max(a, b))\n", "def solve(n, board):\n\tbob_score = [0] * n\n\tbot = 0\n\ttop = sum(board[0])\n\tfor i in range(n):\n\t\ttop -= board[0][i]\n\t\tbob_score[i] = max(bot, top)\n\t\tbot += board[1][i]\n\treturn min(bob_score)\nimport os\nimport io\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\nT = int(input().decode().strip())\nfor t in range(T):\n\tn = int(input().decode().strip())\n\trow1 = [int(x) for x in input().decode().strip().split(' ')]\n\trow2 = [int(x) for x in input().decode().strip().split(' ')]\n\tres1 = solve(n, [row1, row2])\n\tprint(res1)\n", "import sys\nimport math\nlines = []\nis_stdin = False\nis_stdin = True\nif is_stdin:\n\tfor line in sys.stdin:\n\t\tlines.append(line.strip())\nelse:\n\twith open('./input1.txt', 'r') as f:\n\t\tfor line in f.readlines():\n\t\t\tlines.append(line.strip())\nN = int(lines.pop(0))\nwhile N > 0:\n\tN -= 1\n\tn = int(lines.pop(0))\n\ta = lines.pop(0).split(' ')\n\tarr_a = [int(x) for x in a]\n\tb = lines.pop(0).split(' ')\n\tarr_b = [int(x) for x in b]\n\tsum_a = sum(arr_a)\n\ttop_right = sum_a\n\tbottom_left = 0\n\ta_min_b = None\n\tfor i in range(0, len(arr_a)):\n\t\ttop_right -= arr_a[i]\n\t\tif i > 0:\n\t\t\tbottom_left += arr_b[i - 1]\n\t\tcur_b_max = max(top_right, bottom_left)\n\t\tif a_min_b is None:\n\t\t\ta_min_b = cur_b_max\n\t\telif cur_b_max < a_min_b:\n\t\t\ta_min_b = cur_b_max\n\tprint(a_min_b)\n", "for _ in range(int(input())):\n\tn = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\ts1 = sum(a)\n\ts2 = 0\n\tans = 10 ** 9\n\tfor i in range(n):\n\t\ts1 = s1 - a[i]\n\t\tans = min(ans, max(s1, s2))\n\t\ts2 = s2 + b[i]\n\tprint(ans)\n", "import atexit, io, sys, collections, math, heapq, fractions, copy, os, functools\nimport sys\nimport random\nimport collections\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n\ndef f(mat):\n\tif len(mat[0]) == 1:\n\t\treturn 0\n\tans = 10 ** 10\n\tcumul = 0\n\tdp2 = [0 for ii in range(len(mat[0]))]\n\tfor i in range(len(mat[0]) - 1):\n\t\tcumul += mat[1][i]\n\t\tdp2[i] = cumul\n\tdp1 = [0 for ii in range(len(mat[0]))]\n\tcumul = 0\n\tfor i in range(len(mat[0]) - 1, 0, -1):\n\t\tcumul += mat[0][i]\n\t\tdp1[i] = cumul\n\tfor i in range(-1, len(mat[0]) - 1):\n\t\tuu = dp2[i] if i >= 0 else 0\n\t\tvv = dp1[i + 2] if i + 2 < len(dp1) else 0\n\t\tans = min(ans, max(uu, vv))\n\treturn ans\nfor u in range(int(input())):\n\tm = int(input())\n\tmat = [list(map(int, input().split())) for _ in range(2)]\n\tprint(f(mat))\n", "import sys\ninput = sys.stdin.readline\n\ndef solve():\n\tm = int(input())\n\tarr = [list(map(int, input().split())) for _ in range(2)]\n\t(ps1, ps2) = ([0] * m, [0] * m)\n\tv1 = v2 = 0\n\tfor i in range(m):\n\t\tv1 += arr[0][i]\n\t\tv2 += arr[1][i]\n\t\tps1[i] += v1\n\t\tps2[i] += v2\n\tans = min(ps1[-1] - ps1[0], ps2[-1] - arr[1][-1])\n\tfor i in range(1, m - 1):\n\t\tans = min(ans, max(ps2[i - 1], ps1[-1] - ps1[i]))\n\treturn ans\nfor _ in range(int(input())):\n\tprint(solve())\n", "import sys\ninput_file = sys.stdin\noutput_file = sys.stdout\nfor i in range(int(input_file.readline())):\n\tn = int(input_file.readline())\n\trow1 = [int(num) for num in input_file.readline().split()]\n\trow2 = [int(num) for num in input_file.readline().split()]\n\tsum1 = 0\n\tsum2 = sum(row2[:-1])\n\tans = max(sum1, sum2)\n\tfor j in range(n - 1):\n\t\tsum1 += row1[n - 1 - j]\n\t\tsum2 -= row2[n - 2 - j]\n\t\tans = min(ans, max(sum1, sum2))\n\toutput_file.write(str(ans) + '\\n')\n", "import sys\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\ninp = lambda : list(map(int, sys.stdin.readline().rstrip('\\r\\n').split()))\nmod = 10 ** 9 + 7\nMod = 998244353\nINF = float('inf')\nimport math\nfrom bisect import *\nfrom heapq import *\nfrom collections import defaultdict as dd\nfrom collections import OrderedDict as odict\nfrom collections import Counter as cc\nfrom collections import deque\nfrom itertools import groupby\nsys.setrecursionlimit(20 * 20 * 20 * 20 + 10)\n\ndef solve():\n\tn = takein()\n\tmat = [[-1] * n for i in range(2)]\n\tfor i in range(2):\n\t\tarr = takeiar()\n\t\tindex = 0\n\t\tfor j in arr:\n\t\t\tmat[i][index] = j\n\t\t\tindex += 1\n\tif n == 1:\n\t\tprint(0)\n\t\treturn\n\tif n == 2:\n\t\tprint(min(mat[0][1], mat[1][0]))\n\t\treturn\n\tsum = 0\n\tfor i in range(1, n):\n\t\tsum += mat[0][i]\n\tans = sum\n\ttemp = 0\n\tfor i in range(1, n - 1):\n\t\ttemp += mat[1][i - 1]\n\t\tsum -= mat[0][i]\n\t\ttemp1 = max(temp, sum)\n\t\tans = min(temp1, ans)\n\tans = min(ans, temp + mat[1][i])\n\tprint(ans)\n\treturn\n\ndef main():\n\tglobal tt\n\tif not ONLINE_JUDGE:\n\t\tsys.stdin = open('input.txt', 'r')\n\t\tsys.stdout = open('output.txt', 'w')\n\tt = 1\n\tt = takein()\n\tfor tt in range(1, t + 1):\n\t\tsolve()\n\tif not ONLINE_JUDGE:\n\t\tprint('Time Elapsed :', time.time() - start_time, 'seconds')\n\t\tsys.stdout.close()\n\ndef takein():\n\treturn int(sys.stdin.readline().rstrip('\\r\\n'))\n\ndef takesr():\n\treturn sys.stdin.readline().rstrip('\\r\\n')\n\ndef takeiar():\n\treturn list(map(int, sys.stdin.readline().rstrip('\\r\\n').split()))\n\ndef takesar():\n\treturn list(map(str, sys.stdin.readline().rstrip('\\r\\n').split()))\n\ndef takeivr():\n\treturn map(int, sys.stdin.readline().rstrip('\\r\\n').split())\n\ndef takesvr():\n\treturn map(str, sys.stdin.readline().rstrip('\\r\\n').split())\n\ndef ispalindrome(s):\n\treturn s == s[::-1]\n\ndef invert(bit_s):\n\ttemp = int(bit_s, 2)\n\tinverse_s = temp ^ 2 ** (len(bit_s) + 1) - 1\n\trslt = bin(inverse_s)[3:]\n\treturn str(rslt)\n\ndef counter(a):\n\tq = [0] * max(a)\n\tfor i in range(len(a)):\n\t\tq[a[i] - 1] = q[a[i] - 1] + 1\n\treturn q\n\ndef counter_elements(a):\n\tq = dict()\n\tfor i in range(len(a)):\n\t\tif a[i] not in q:\n\t\t\tq[a[i]] = 0\n\t\tq[a[i]] = q[a[i]] + 1\n\treturn q\n\ndef string_counter(a):\n\tq = [0] * 26\n\tfor i in range(len(a)):\n\t\tq[ord(a[i]) - 97] = q[ord(a[i]) - 97] + 1\n\treturn q\n\ndef factorial(n, m=1000000007):\n\tq = 1\n\tfor i in range(n):\n\t\tq = q * (i + 1) % m\n\treturn q\n\ndef factors(n):\n\tq = []\n\tfor i in range(1, int(n ** 0.5) + 1):\n\t\tif n % i == 0:\n\t\t\tq.append(i)\n\t\t\tq.append(n // i)\n\treturn list(sorted(list(set(q))))\n\ndef prime_factors(n):\n\tq = []\n\twhile n % 2 == 0:\n\t\tq.append(2)\n\t\tn = n // 2\n\tfor i in range(3, int(n ** 0.5) + 1, 2):\n\t\twhile n % i == 0:\n\t\t\tq.append(i)\n\t\t\tn = n // i\n\tif n > 2:\n\t\tq.append(n)\n\treturn list(sorted(q))\n\ndef transpose(a):\n\t(n, m) = (len(a), len(a[0]))\n\tb = [[0] * n for i in range(m)]\n\tfor i in range(m):\n\t\tfor j in range(n):\n\t\t\tb[i][j] = a[j][i]\n\treturn b\n\ndef power_two(x):\n\treturn x and (not x & x - 1)\n\ndef ceil(a, b):\n\treturn -(-a // b)\n\ndef seive(n):\n\ta = [1]\n\tprime = [True for i in range(n + 1)]\n\tp = 2\n\twhile p * p <= n:\n\t\tif prime[p] == True:\n\t\t\tfor i in range(p ** 2, n + 1, p):\n\t\t\t\tprime[i] = False\n\t\tp = p + 1\n\tfor p in range(2, n + 1):\n\t\tif prime[p]:\n\t\t\ta.append(p)\n\treturn a\n\ndef pref(li):\n\tpref_sum = [0]\n\tfor i in li:\n\t\tpref_sum.append(pref_sum[-1] + i)\n\treturn pref_sum\n\ndef kadane(x):\n\tsum_so_far = 0\n\tcurrent_sum = 0\n\tfor i in x:\n\t\tcurrent_sum += i\n\t\tif current_sum < 0:\n\t\t\tcurrent_sum = 0\n\t\telse:\n\t\t\tsum_so_far = max(sum_so_far, current_sum)\n\treturn sum_so_far\n\ndef binary_search(li, val):\n\tans = -1\n\tlb = 0\n\tub = len(li) - 1\n\twhile lb <= ub:\n\t\tmid = (lb + ub) // 2\n\t\tif li[mid] > val:\n\t\t\tub = mid - 1\n\t\telif val > li[mid]:\n\t\t\tlb = mid + 1\n\t\telse:\n\t\t\tans = mid\n\t\t\tbreak\n\treturn ans\n\ndef upper_bound(li, num):\n\tanswer = -1\n\tstart = 0\n\tend = len(li) - 1\n\twhile start <= end:\n\t\tmiddle = (end + start) // 2\n\t\tif li[middle] <= num:\n\t\t\tanswer = middle\n\t\t\tstart = middle + 1\n\t\telse:\n\t\t\tend = middle - 1\n\treturn answer\n\ndef lower_bound(li, num):\n\tanswer = -1\n\tstart = 0\n\tend = len(li) - 1\n\twhile start <= end:\n\t\tmiddle = (end + start) // 2\n\t\tif li[middle] >= num:\n\t\t\tanswer = middle\n\t\t\tend = middle - 1\n\t\telse:\n\t\t\tstart = middle + 1\n\treturn answer\nONLINE_JUDGE = __debug__\nif ONLINE_JUDGE:\n\tinput = sys.stdin.readline\nmain()\n", "def main(n, a, b) -> int:\n\tpref_a = [0]\n\tpref_b = [0]\n\tsuf_a = [0]\n\tsuf_b = [0]\n\tfor i in range(n):\n\t\tpref_a.append(pref_a[-1] + a[i])\n\t\tpref_b.append(pref_b[-1] + b[i])\n\tpref_a.append(pref_a[-1])\n\tpref_b.append(pref_b[-1])\n\tfor i in range(n - 1, -1, -1):\n\t\tsuf_a.append(suf_a[-1] + a[i])\n\t\tsuf_b.append(suf_b[-1] + b[i])\n\tsuf_a.append(suf_a[-1])\n\tsuf_b.append(suf_b[-1])\n\tsuf_a.reverse()\n\tsuf_b.reverse()\n\tbob_score = float('inf')\n\tfor i in range(1, n + 1):\n\t\t_alice_score = pref_a[i] + suf_b[i]\n\t\t_bob_score = max(pref_b[i - 1], suf_a[i + 1])\n\t\tif bob_score > _bob_score:\n\t\t\tbob_score = _bob_score\n\treturn bob_score\nt = int(input())\nans = []\nfor i in range(t):\n\tm = int(input())\n\ta = [int(i) for i in input().split(' ')]\n\tb = [int(i) for i in input().split(' ')]\n\tans.append(main(m, a, b))\nfor i in ans:\n\tprint(i)\n", "import sys\nfor _ in range(int(input())):\n\tm = int(input())\n\ta = []\n\ta.append([int(i) for i in input().split()])\n\ta.append([int(i) for i in input().split()])\n\tfor i in range(1, m):\n\t\tfor j in range(2):\n\t\t\ta[j][i] += a[j][i - 1]\n\tscore = sys.maxsize\n\tfor i in range(m):\n\t\tscore_i = a[0][m - 1] - a[0][i]\n\t\tif i != 0:\n\t\t\tscore_i = max(score_i, a[1][i - 1])\n\t\tscore = min(score, score_i)\n\tprint(score)\n", "for _ in range(int(input())):\n\tm = int(input())\n\ta1 = list(map(int, input().split()))\n\ta2 = list(map(int, input().split()))\n\ts = sum(a1)\n\t(h, x) = ([], 0)\n\tfor i in range(m):\n\t\ts -= a1[i]\n\t\th.append(max(s, x))\n\t\tx += a2[i]\n\tif len(h) == 0:\n\t\tprint(0)\n\telse:\n\t\tprint(min(h))\n", "def gcd(a, b):\n\tif a % b == 0:\n\t\treturn b\n\telse:\n\t\treturn gcd(b, a % b)\n\ndef lcm(a, b):\n\treturn a * b // gcd(a, b)\ntestcases = 1\ntestcases = int(input())\nfor _ in range(testcases):\n\tm = int(input())\n\trow1 = [int(x) for x in input().split()]\n\trow2 = [int(x) for x in input().split()]\n\tpref = [0]\n\tsuf = [0]\n\tfor i in row2:\n\t\tpref.append(pref[-1] + i)\n\tfor i in range(m - 1, -1, -1):\n\t\tsuf.append(suf[-1] + row1[i])\n\tmini = 1000000000000000.0\n\tfor i in range(m):\n\t\tmini = min(mini, max(pref[i], suf[m - i - 1]))\n\tprint(mini)\n", "n = int(input())\nfor task in range(n):\n\tm = int(input())\n\ts1 = [int(num1) for num1 in input().split()]\n\ts2 = [int(num2) for num2 in input().split()]\n\tres = []\n\tsum1 = sum(s1)\n\tsum2 = 0\n\tfor i in range(m):\n\t\tsum1 -= s1[i]\n\t\tres.append(max(sum1, sum2))\n\t\tsum2 += s2[i]\n\tprint(min(res))\n", "import heapq, math\nfrom collections import defaultdict, deque\nfrom os import getcwd\nfrom itertools import permutations\nimport sys, os.path\nif os.path.exists('C:/Users/Dhanush/Desktop/cp/input.txt'):\n\tsys.stdout = open('C:/Users/Dhanush/Desktop/cp/output.txt', 'w')\n\tsys.stdin = open('C:/Users/Dhanush/Desktop/cp/input.txt', 'r')\ninput = sys.stdin.readline\n\ndef psum(arr, i, j):\n\tif i > j:\n\t\treturn 0\n\ts = arr[j]\n\tif i - 1 >= 0:\n\t\ts -= arr[i - 1]\n\treturn s\ntc = int(input())\nfor _ in range(tc):\n\tm = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\t(s1, s2) = (0, 0)\n\tprea = []\n\tpreb = []\n\tfor i in range(m):\n\t\ts1 += a[i]\n\t\ts2 += b[i]\n\t\tprea.append(s1)\n\t\tpreb.append(s2)\n\tans = float('inf')\n\tfor i in range(1, m - 1):\n\t\tc1 = psum(prea, i + 1, m - 1)\n\t\tc2 = psum(preb, 0, i - 1)\n\t\tcur = max(c1, c2)\n\t\tans = min(ans, cur)\n\tans = min(ans, psum(prea, 1, m - 1), psum(preb, 0, m - 2))\n\tprint(ans)\n", "import math\n\ndef pn(x, y, m):\n\ts1 = 0\n\ts2 = 0\n\tans = math.inf\n\tfor i in range(m):\n\t\ts1 += x[i]\n\tfor i in range(m):\n\t\ts1 -= x[i]\n\t\tans = min(ans, max(s1, s2))\n\t\ts2 += y[i]\n\treturn ans\nn = int(input())\nfor i in range(n):\n\tm = int(input())\n\tx = list(map(int, input().split()))[:m]\n\ty = list(map(int, input().split()))[:m]\n\tprint(pn(x, y, m))\n", "from collections import deque\nimport heapq\nfrom math import sqrt\nimport operator\nfrom operator import itemgetter\nimport sys\nimport copy\ninf_var = 0\nif inf_var == 1:\n\tinf = open('input.txt', 'r')\nelse:\n\tinf = sys.stdin\ninput = inf.readline\n\ndef read_one_int():\n\treturn int(input().rstrip('\\n'))\n\ndef read_one_float():\n\treturn float(input().rstrip('\\n'))\n\ndef read_list_of_ints():\n\tres = [int(val) for val in input().rstrip('\\n').split(' ')]\n\treturn res\n\ndef read_str():\n\treturn input().rstrip()\n\ndef to_left_diag(i, j):\n\treturn i + j\n\ndef to_right_diag(i, j):\n\treturn i - j\n\nclass Vertex:\n\n\tdef __init__(self):\n\t\tself.next = {}\n\t\tself.terminal = False\n\t\tself.cnt = 1\n\ndef add_str(trie, cur_str):\n\tvertices_cnt = 0\n\tcur_node = trie\n\tfor ch in cur_str:\n\t\tif ch in cur_node.next:\n\t\t\tcur_node = cur_node.next[ch]\n\t\t\tcur_node.cnt += 1\n\t\telse:\n\t\t\tcur_node.next[ch] = Vertex()\n\t\t\tvertices_cnt += 1\n\t\t\tcur_node = cur_node.next[ch]\n\tcur_node.terminal = True\n\treturn vertices_cnt\n\ndef main():\n\ttests = read_one_int()\n\tfor _ in range(tests):\n\t\tm = read_one_int()\n\t\trow_1 = read_list_of_ints()\n\t\trow_2 = read_list_of_ints()\n\t\tcur_res = 10 ** 10\n\t\tfor i in range(1, m):\n\t\t\trow_1[i] += row_1[i - 1]\n\t\t\trow_2[i] += row_2[i - 1]\n\t\tfor i in range(m):\n\t\t\tleft_1 = row_1[m - 1] - row_1[i]\n\t\t\tif i > 0:\n\t\t\t\tleft_2 = row_2[i - 1]\n\t\t\telse:\n\t\t\t\tleft_2 = 0\n\t\t\tcur_max = max(left_1, left_2)\n\t\t\tcur_res = min(cur_res, cur_max)\n\t\tprint(cur_res)\nmain()\n", "import sys\ninput = lambda : sys.stdin.readline()\nint_arr = lambda : list(map(int, input().split()))\nstr_arr = lambda : list(map(str, input().split()))\nget_str = lambda : map(str, input().split())\nget_int = lambda : map(int, input().split())\nget_flo = lambda : map(float, input().split())\nmod = 1000000007\n\ndef solve(n, a, b):\n\tfor i in range(n - 2, -1, -1):\n\t\ta[i] += a[i + 1]\n\tfor i in range(1, n):\n\t\tb[i] += b[i - 1]\n\tans = 0\n\tfor i in range(1, n):\n\t\tans = max(ans, min(a[i], b[i - 1]))\n\tprint(ans)\nfor _ in range(int(input())):\n\tn = int(input())\n\ta = int_arr()\n\tb = int_arr()\n\tsolve(n, a, b)\n", "for nt in range(int(input())):\n\tm = int(input())\n\ta = []\n\ta.append(list(map(int, input().split())))\n\ta.append(list(map(int, input().split())))\n\tif m == 1:\n\t\tprint(0)\n\t\tcontinue\n\tprefix = [[0 for i in range(m)] for j in range(2)]\n\tsuffix = [[0 for i in range(m)] for j in range(2)]\n\tprefix[0][0] = a[0][0]\n\tprefix[1][0] = a[1][0]\n\tfor i in range(1, m):\n\t\tprefix[0][i] = prefix[0][i - 1] + a[0][i]\n\t\tprefix[1][i] = prefix[1][i - 1] + a[1][i]\n\tsuffix[0][-1] = a[0][-1]\n\tsuffix[1][-1] = a[1][-1]\n\tfor i in range(m - 2, -1, -1):\n\t\tsuffix[0][i] = suffix[0][i + 1] + a[0][i]\n\t\tsuffix[1][i] = suffix[1][i + 1] + a[1][i]\n\tans = min(suffix[0][1], prefix[1][-2])\n\tfor i in range(1, m - 1):\n\t\tans = min(ans, max(prefix[1][i - 1], suffix[0][i + 1]))\n\tprint(ans)\n", "from itertools import product\nimport itertools\nimport math\nimport sys\nimport heapq\nfrom collections import deque\nMOD = 1000000000007\n\ndef find(parent, i):\n\tif parent[i] != i:\n\t\tparent[i] = find(parent, parent[i])\n\treturn parent[i]\n\ndef union(parent, rank, xx, yy):\n\tx = find(parent, xx)\n\ty = find(parent, yy)\n\tif rank[x] > rank[y]:\n\t\tparent[y] = x\n\telif rank[y] > rank[x]:\n\t\tparent[x] = y\n\telse:\n\t\tparent[y] = x\n\t\trank[x] += 1\nans = 0\nK = int(sys.stdin.readline().strip())\nx = 0\ny = 0\nfor _ in range(K):\n\tm = int(sys.stdin.readline().strip())\n\tmat = []\n\tl = list(map(int, sys.stdin.readline().strip().split()))\n\tM = sum(l)\n\tmat.append(l)\n\tl = list(map(int, sys.stdin.readline().strip().split()))\n\tM = max(M, sum(l))\n\tmat.append(l)\n\tp1 = [0]\n\tp2 = [0]\n\tfor i in range(m - 1, -1, -1):\n\t\tp1.append(p1[-1] + mat[0][i])\n\tp1.reverse()\n\tfor i in range(m):\n\t\tp2.append(p2[-1] + mat[1][i])\n\tans = M\n\tfor i in range(m):\n\t\tans = min(ans, max(p1[i + 1], p2[i]))\n\tprint(ans)\n", "___t = int(input())\nfor t___ in range(___t):\n\tm = int(input())\n\tss = input().split()\n\ta = [0] * m\n\tfor i in range(m):\n\t\ta[i] = int(ss[i])\n\tss = input().split()\n\tb = [0] * m\n\tbsum = 0\n\tfor i in range(m):\n\t\tb[i] = int(ss[i])\n\t\tbsum += b[i]\n\tres = 0\n\tasum = 0\n\tfor i in range(m - 1):\n\t\tasum += a[m - i - 1]\n\t\tbsum -= b[m - i - 1]\n\t\tres = max(res, min(asum, bsum))\n\tprint(res)\n", "from itertools import accumulate\n\ndef readline():\n\treturn list(map(int, input().split()))\n\ndef solve():\n\tm = int(input())\n\ta1 = list(accumulate(reversed(readline()), initial=0))\n\ta2 = list(accumulate(readline(), initial=0))\n\tprint(min((max(a1[i], a2[m - 1 - i]) for i in range(m))))\nt = int(input())\nfor __ in range(t):\n\tsolve()\n", "from __future__ import division, print_function\nimport os\nimport sys\nfrom io import BytesIO, IOBase\nif sys.version_info[0] < 3:\n\tfrom __builtin__ import xrange as range\n\tfrom future_builtins import ascii, filter, hex, map, oct, zip\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n\ndef print(*args, **kwargs):\n\t(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))\n\tat_start = True\n\tfor x in args:\n\t\tif not at_start:\n\t\t\tfile.write(sep)\n\t\tfile.write(str(x))\n\t\tat_start = False\n\tfile.write(kwargs.pop('end', '\\n'))\n\tif kwargs.pop('flush', False):\n\t\tfile.flush()\nif sys.version_info[0] < 3:\n\t(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))\nelse:\n\t(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nimport collections, string, bisect, re, random, queue, itertools, statistics, math\nfrom collections import *\nfrom bisect import *\nfrom string import *\nfrom itertools import *\nfrom statistics import *\nfrom math import *\nfrom re import *\nfrom queue import *\n\nclass Stack:\n\n\tdef __init__(self):\n\t\tself.items = []\n\n\tdef push(self, item):\n\t\tself.items.append(item)\n\n\tdef pop(self):\n\t\treturn self.items.pop()\n\n\tdef empty(self):\n\t\treturn self.items == []\n\n\tdef size(self):\n\t\treturn len(self.items)\n\n\tdef at(self, idx):\n\t\ttry:\n\t\t\treturn self.items[idx]\n\t\texcept:\n\t\t\treturn -1\n\nclass priority_queue(object):\n\n\tdef __init__(self):\n\t\tself.queue = []\n\n\tdef __str__(self):\n\t\treturn ' '.join([str(i) for i in self.queue])\n\n\tdef empty(self):\n\t\treturn len(self.queue) == 0\n\n\tdef push(self, data):\n\t\tself.queue.append(data)\n\n\tdef pop(self):\n\t\ttry:\n\t\t\tmax = 0\n\t\t\tfor i in range(len(self.queue)):\n\t\t\t\tif self.queue[i] > self.queue[max]:\n\t\t\t\t\tmax = i\n\t\t\titem = self.queue[max]\n\t\t\tdel self.queue[max]\n\t\t\treturn item\n\t\texcept IndexError:\n\t\t\tprint()\n\t\t\texit()\nmod = int(1000000000.0 + 7)\nimax = float('inf')\nimin = float('-inf')\ntrue = True\nfalse = False\nN = int(100000.0)\nnone = None\ninp = lambda : input()\nI = lambda : int(inp())\nM = lambda : map(int, inp().split())\nMS = lambda : map(str, inp().split())\nS = lambda : list(MS())\nL = lambda : list(M())\n\ndef IO():\n\ttry:\n\t\tsys.stdin = open('input.txt', 'r')\n\t\tsys.stdout = open('uttar.txt', 'w')\n\texcept:\n\t\tpass\nIO()\n\nclass helper:\n\n\tdef first(self, arr):\n\t\treturn arr[0]\n\n\tdef second(self, arr):\n\t\treturn arr[1]\n\n\tdef is_sorted(self, arr):\n\t\treturn arr == sorted(arr)\n\ndef kabraji_ka_totka():\n\tm = I()\n\tmat = [L() for i in range(2)]\n\tif m == 1:\n\t\tprint(0)\n\t\treturn\n\tmax_range = sum(mat[0]) - mat[0][0]\n\tres = max_range\n\ty_axis = 0\n\tfor i in range(1, m):\n\t\ty_axis += mat[1][i - 1]\n\t\tmax_range -= mat[0][i]\n\t\tres = min(res, max(max_range, y_axis))\n\tprint(max(res, 0))\ncase = 1\ncase = I()\nfor i in range(case):\n\tkabraji_ka_totka()\n", "import sys\ninput = sys.stdin.readline\nfor test in range(int(input().strip())):\n\tn = int(input().strip())\n\tls1 = list(map(int, input().strip().split()))\n\tlis2 = list(map(int, input().strip().split()))\n\tnlis = []\n\tc = d = 0\n\tfor i in range(n):\n\t\tc += ls1[i]\n\t\tls1[i] = c\n\t\td += lis2[i]\n\t\tnlis.append(d)\n\tans = ls1[-1] + nlis[-1]\n\tfor i in range(n):\n\t\tans = min(ans, max(ls1[-1] - ls1[i], nlis[i] - lis2[i]))\n\tprint(ans)\n", "t = int(input())\nwhile t:\n\tt = t - 1\n\tm = int(input())\n\ta1 = list(map(int, input().split()))\n\ta2 = list(map(int, input().split()))\n\ty = sum(a1)\n\tx = 0\n\tans = 10000000000000\n\tfor i in range(m):\n\t\ty -= a1[i]\n\t\tans = min(ans, max(x, y))\n\t\tx += a2[i]\n\tprint(ans)\n", "def solve(n, a, b):\n\tsa = sum(a)\n\tsb = sum(b)\n\tca = 0\n\tcb = 0\n\tfor i in range(n):\n\t\tif i == 0:\n\t\t\tx = sa - a[i]\n\t\t\tca = a[0]\n\t\t\tcb = b[0]\n\t\telse:\n\t\t\ty = max(sa - ca - a[i], cb)\n\t\t\tx = min(x, y)\n\t\t\tca += a[i]\n\t\t\tcb += b[i]\n\treturn x\nt = int(input())\nfor i in range(t):\n\tn = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tprint(solve(n, a, b))\n", "for _ in range(int(input())):\n\tm = int(input())\n\tl1 = list(map(int, input().split()))\n\tl2 = list(map(int, input().split()))\n\tsum1 = sum(l1) - l1[0]\n\tsum2 = 0\n\tres1 = sum(l1) - l1[0]\n\tres2 = 0\n\tfor i in range(1, m):\n\t\tsum1 -= l1[i]\n\t\tsum2 += l2[i - 1]\n\t\tif max(sum1, sum2) < max(res1, res2):\n\t\t\tres1 = sum1\n\t\t\tres2 = sum2\n\tprint(max(res1, res2))\n", "from itertools import accumulate\nt = int(input())\nfor _ in range(t):\n\tm = int(input())\n\ta_1 = list(accumulate([int(i) for i in input().split()]))\n\ta_2 = list(accumulate([int(i) for i in input().split()]))\n\tprint(min([max(a_2[i - 1] if i else 0, a_1[m - 1] - a_1[i]) for i in range(m)]) if m > 1 else 0)\n", "for i in range(int(input())):\n\tm = int(input())\n\tarr = []\n\tarr.append(list(map(int, input().split())))\n\tarr.append(list(map(int, input().split())))\n\tans = 100000000000.0\n\ts1 = sum(arr[0])\n\ts2 = 0\n\tif m == 1:\n\t\tprint(0)\n\t\tcontinue\n\tfor j in range(m):\n\t\ts1 -= arr[0][j]\n\t\tans = min(ans, max(s1, s2))\n\t\ts2 += arr[1][j]\n\tprint(ans)\n", "import sys\nfrom math import factorial, gcd\nfrom collections import Counter, deque, defaultdict\nfrom bisect import bisect_left, bisect_right\nfrom heapq import heappop, heappush, heapify, nlargest, nsmallest\nfrom itertools import groupby\nfrom copy import deepcopy\nMOD = 10 ** 9 + 7\nINF = float('inf')\nrl = lambda : list(map(int, sys.stdin.readline().split()))\nrs = lambda : sys.stdin.readline().strip()\nfor _ in range(int(input())):\n\tm = int(input())\n\tmatrix = [rl() for _ in range(2)]\n\tif m == 1:\n\t\tprint(0)\n\t\tcontinue\n\t(psum1, psum2) = ([0], [0])\n\tfor j in range(m - 1, -1, -1):\n\t\tpsum1.append(psum1[-1] + matrix[0][j])\n\tfor j in range(m):\n\t\tpsum2.append(psum2[-1] + matrix[1][j])\n\tpsum1.reverse()\n\tpsum1.append(0)\n\tpsum2.append(0)\n\tres = INF\n\tfor i in range(1, m + 1):\n\t\tval = max(psum1[i], psum2[i - 1])\n\t\tres = min(res, val)\n\tprint(res)\n", "import sys\ntestcases = int(input())\nwhile testcases > 0:\n\tn = int(input())\n\trow1 = list(map(int, sys.stdin.readline().split()))\n\trow2 = list(map(int, sys.stdin.readline().split()))\n\ts1 = sum(row1) - row1[0]\n\ts2 = 0\n\ta = s1\n\tb = 0\n\tfor i in range(1, n):\n\t\ts2 += row2[i - 1]\n\t\ts1 -= row1[i]\n\t\tb = max(s1, s2)\n\t\ta = min(b, a)\n\tprint(a)\n\ttestcases -= 1\n", "for t in range(int(input())):\n\tm = int(input())\n\ta1 = list(map(int, input().split()))\n\ta2 = list(map(int, input().split()))\n\tans = 10 ** 10\n\tsm1 = sum(a1)\n\tsm2 = 0\n\tfor i in range(m):\n\t\tsm1 -= a1[i]\n\t\tans = min(ans, max(sm2, sm1))\n\t\tsm2 += a2[i]\n\tprint(ans)\n", "for _ in range(int(input())):\n\tn = int(input())\n\ts1 = [int(x) for x in input().split()]\n\ts2 = [int(x) for x in input().split()]\n\tpr1 = [0]\n\tpr2 = [0]\n\tfor i in range(n):\n\t\tpr1.append(pr1[-1] + s1[i])\n\t\tpr2.append(pr2[-1] + s2[i])\n\tbest = pr2[-1] - s2[-1]\n\tfor i in range(n):\n\t\tbest = min(best, max(pr1[-1] - pr1[i + 1], pr2[i]))\n\tprint(best)\n", "R = lambda : map(int, input().split())\n(t,) = R()\nwhile t:\n\tt -= 1\n\tR()\n\ta = (*R(),)\n\tu = sum(a)\n\tv = 0\n\tr = 1000000000.0\n\tfor (x, y) in zip(a, R()):\n\t\tu -= x\n\t\tr = min(r, max(u, v))\n\t\tv += y\n\tprint(r)\n", "from itertools import accumulate\nfor _ in range(int(input())):\n\tm = int(input())\n\ta1 = list(map(int, input().split()))\n\ta2 = list(map(int, input().split()))\n\tc1 = list(accumulate([0] + a1[::-1]))\n\tc2 = list(accumulate([0] + a2))\n\tx = float('inf')\n\tfor i in range(m):\n\t\ts = max(c2[i], c1[-i - 2])\n\t\tif s < x:\n\t\t\tx = s\n\tprint(x)\n", "def solve(m, x):\n\tpcl = [0] * m\n\tfor i in range(1, m):\n\t\tpcl[i] = pcl[i - 1] + x[1][i - 1]\n\tpcu = [0] * m\n\tfor i in range(m - 2, -1, -1):\n\t\tpcu[i] = pcu[i + 1] + x[0][i + 1]\n\tr = 2 ** 65\n\tfor i in range(m):\n\t\tr = min(r, max(pcl[i], pcu[i]))\n\tprint(r)\nt = int(input())\nfor i in range(t):\n\tm = int(input())\n\tx = [[int(j) for j in input().split()] for _ in '12']\n\tsolve(m, x)\n", "import sys\ninput = sys.stdin.readline\nfrom pprint import pprint\nINF = 1 << 63\n\ndef do():\n\timport itertools\n\n\tclass CumSum1D:\n\n\t\tdef __init__(self):\n\t\t\tpass\n\n\t\tdef load(self, a):\n\t\t\tself.sdat = list(itertools.accumulate(itertools.chain([0], a)))\n\n\t\tdef query(self, l, r):\n\t\t\treturn self.sdat[r] - self.sdat[l]\n\tn = int(input())\n\tdat1 = list(map(int, input().split()))\n\tdat2 = list(map(int, input().split()))\n\ts1 = CumSum1D()\n\ts2 = CumSum1D()\n\ts1.load(dat1)\n\ts2.load(dat2)\n\tres = INF\n\tfor i in range(n):\n\t\tscore = max(s1.query(i + 1, n), s2.query(0, i))\n\t\tres = min(res, score)\n\tprint(res)\nq = int(input())\nfor _ in range(q):\n\tdo()\n", "from sys import stdin, stdout\n\ndef INPUT():\n\treturn list((int(i) for i in stdin.readline().split()))\n\ndef inp():\n\treturn stdin.readline()\n\ndef out(x):\n\treturn stdout.write(x)\nimport math\nINT_MAX = 10 ** 13\nfrom bisect import bisect_left\nimport sys\nMOD = 10 ** 9 + 7\ninf = MOD ** 2\nfor _ in range(int(input())):\n\tn = int(input())\n\tA = INPUT()\n\tB = INPUT()\n\tif n == 1:\n\t\tprint(0)\n\t\tcontinue\n\ts = sum(A) + sum(B)\n\tscore = 0\n\tsumA = [0] * n\n\tsumB = [0] * n\n\tsumB[0] = B[0]\n\tsumA[0] = A[0]\n\tans = inf\n\tfor i in range(1, n):\n\t\tsumA[i] = sumA[i - 1] + A[i]\n\t\tsumB[i] = sumB[i - 1] + B[i]\n\tfor i in range(n):\n\t\tif i > 0:\n\t\t\tk = max(sumA[-1] - sumA[i], sumB[i - 1])\n\t\telse:\n\t\t\tk = sumA[-1] - sumA[0]\n\t\tans = min(ans, k)\n\tprint(ans)\n", "def rows_of_coins(m: int, rows: list):\n\tif m == 1:\n\t\treturn 0\n\tif m == 2:\n\t\treturn min(rows[0][1], rows[1][0])\n\tarr = [[0] * m, [0] * m]\n\tarr[1][0] = rows[1][0]\n\tarr[0][m - 1] = rows[0][m - 1]\n\tfor i in range(1, m - 1):\n\t\tarr[1][i] = arr[1][i - 1] + rows[1][i]\n\t\tarr[0][m - 1 - i] = arr[0][m - i] + rows[0][m - 1 - i]\n\tmin_coins = 10 ** 4 * m\n\tfor i in range(2, m):\n\t\tcur_min = max(arr[0][i], arr[1][i - 2])\n\t\tif cur_min < min_coins:\n\t\t\tmin_coins = cur_min\n\treturn min(min_coins, arr[0][1], arr[1][-2])\nt = int(input())\nfor i in range(t):\n\tm = int(input())\n\trows = [list(map(int, input().split(' '))), list(map(int, input().split(' ')))]\n\tprint(rows_of_coins(m, rows))\n", "for _ in range(int(input())):\n\tn = int(input())\n\tarr = list(map(int, input().split()))\n\tbrr = list(map(int, input().split()))\n\tfor i in range(1, n):\n\t\tarr[i] += arr[i - 1]\n\t\tbrr[i] += brr[i - 1]\n\tans = arr[-1] - arr[0]\n\tfor i in range(1, n):\n\t\tans = min(ans, max(arr[-1] - arr[i], brr[i - 1]))\n\tprint(ans)\n", "def get_t(ot):\n\tn = len(ot[0])\n\ttt = [0] * n\n\ttb = [0] * n\n\tst = 0\n\tsb = 0\n\tt = [tt, tb]\n\tfor i in range(n - 1, -1, -1):\n\t\tsb += ot[1][i]\n\t\tst = ot[0][i] + max(sb, st)\n\t\tt[0][i] = st\n\t\tt[1][i] = sb\n\treturn t\n\ndef sol(ot):\n\tn = len(ot[0])\n\tax = 0\n\tay = 0\n\topt = -1\n\topt_id = -1\n\tt = [0] * n\n\tst = 0\n\tb = [0] * n\n\tsb = 0\n\tfor i in range(0, n):\n\t\tst += ot[0][-i - 1]\n\t\tsb += ot[1][i]\n\t\tt[-i - 1] = st\n\t\tb[i] = sb\n\tfor i in range(n):\n\t\tcur = 0\n\t\tif i < n - 1:\n\t\t\tcur = t[i + 1]\n\t\tif i > 0:\n\t\t\tcur = max(b[i - 1], cur)\n\t\tif cur < opt or opt == -1:\n\t\t\topt = cur\n\t\t\topt_id = i\n\tprint(opt)\nfor _ in range(int(input())):\n\tn = int(input())\n\tt1 = list(map(int, input().split()))\n\tt2 = list(map(int, input().split()))\n\tot = [t1, t2]\n\tsol(ot)\n", "import sys\nimport math\nmod = 10 ** 9 + 7\nLI = lambda : [int(k) for k in input().split()]\ninput = lambda : sys.stdin.readline().rstrip()\nIN = lambda : int(input())\nS = lambda : input()\nr = range\nfor t in r(IN()):\n\tm = IN()\n\tarr = []\n\ttop = LI()\n\tbottom = LI()\n\tif m == 1:\n\t\tprint(0)\n\t\tcontinue\n\tpresum = 0\n\tfor i in reversed(range(m)):\n\t\tpresum += top[i]\n\t\ttop[i] = presum\n\tpresum = 0\n\tfor i in range(m):\n\t\tpresum += bottom[i]\n\t\tbottom[i] = presum\n\tans = min(top[1], bottom[m - 2])\n\tfor i in range(1, m - 1):\n\t\tans = min(ans, max(top[i + 1], bottom[i - 1]))\n\tprint(ans)\n", "import sys\nfrom collections import Counter\nimport math\nimport bisect\nimport heapq\nfrom itertools import combinations\nfrom itertools import accumulate\nnum_cases = int(sys.stdin.readline().strip())\nfor case in range(1, num_cases + 1):\n\tM = int(sys.stdin.readline().strip())\n\tone_row = list(map(int, sys.stdin.readline().split()))\n\ttwo_row = list(map(int, sys.stdin.readline().split()))\n\tacc_one = list(accumulate(one_row))\n\tacc_two = list(accumulate(two_row))\n\tresult = float('inf')\n\tfor down in range(M):\n\t\tif down == 0:\n\t\t\tvalue = acc_one[M - 1] - acc_one[0]\n\t\telif down == M - 1:\n\t\t\tvalue = acc_two[M - 2]\n\t\telse:\n\t\t\tfirst = acc_one[M - 1] - acc_one[down]\n\t\t\tsecond = acc_two[down - 1]\n\t\t\tvalue = max(first, second)\n\t\tresult = min(result, value)\n\tprint(result)\n", "import sys\nimport math\nimport heapq\nfrom collections import defaultdict as dd\nfrom collections import OrderedDict as od\nfrom collections import deque\nfrom itertools import permutations as pp\nfrom itertools import combinations as cc\nfrom sys import stdin\nfrom functools import cmp_to_key\nfrom functools import lru_cache\nfrom bisect import bisect_left as bs_l\nfrom bisect import bisect_right as bs_r\ninput = sys.stdin.readline\nmod = 10 ** 9 + 7\nsys.setrecursionlimit(10 ** 5)\nT = int(input())\nfor _ in range(T):\n\tn = int(input())\n\tans = 10 ** 9\n\tmat = []\n\tfor i in range(2):\n\t\tmat.append(list(map(int, input().split())))\n\t(x, y) = (0, 0)\n\tfor i in range(2):\n\t\tfor j in range(n):\n\t\t\tif i == 0:\n\t\t\t\tx += mat[i][j]\n\tfor i in range(n):\n\t\tx -= mat[0][i]\n\t\tans = min(ans, max(x, y))\n\t\ty += mat[1][i]\n\tprint(ans)\n", "for _ in range(int(input())):\n\tn = int(input())\n\tl = list(map(int, input().split()))\n\tl1 = list(map(int, input().split()))\n\ttsl = sum(l)\n\tres = 10 ** 10\n\tfor i in range(n):\n\t\ttsl = tsl - l[i]\n\t\tif i == 0:\n\t\t\tans2 = 0\n\t\telse:\n\t\t\tans2 += l1[i - 1]\n\t\tans = max(tsl, ans2)\n\t\tres = min(res, ans)\n\tprint(res)\n", "import sys\ninput = sys.stdin.readline\nt = []\nfor _ in range(int(input())):\n\tn = int(input())\n\ta = [int(i) for i in input().split()]\n\tb = [int(i) for i in input().split()]\n\t(res, u, d, up, do) = (float('inf'), 0, 0, [], [])\n\tfor i in range(n):\n\t\tu += a[i]\n\t\td += b[i]\n\t\tup += [u]\n\t\tdo += [d]\n\tfor i in range(n):\n\t\tp = max(u - up[i], do[i - 1] * (i != 0))\n\t\tres = min(res, p)\n\tt += [res]\nfor k in t:\n\tprint(k)\n", "import sys\ninput = sys.stdin\noutput = sys.stdout\nN = int(input.readline().strip())\nfor x in range(N):\n\tOB = 999999999999999999999999999999999999999999\n\tC = int(input.readline().strip())\n\trow1 = [int(num) for num in input.readline().split()]\n\trow2 = [int(num) for num in input.readline().split()]\n\ttop = 0\n\tbottom = 0\n\tfor i in range(C):\n\t\ttop += row1[i]\n\tfor i in range(C):\n\t\ttop -= row1[i]\n\t\tif i > 0:\n\t\t\tbottom += row2[i - 1]\n\t\tif top >= bottom:\n\t\t\tif top < OB:\n\t\t\t\tOB = top\n\t\telif bottom < OB:\n\t\t\tOB = bottom\n\toutput.write('%d\\n' % OB)\n", "import sys, math\ninf = math.inf\nsys.setrecursionlimit(10 ** 9)\ninput = sys.stdin.readline\na = int(input())\nfor _ in range(a):\n\tm = int(input())\n\tl = [list(map(int, input().split())) for i in range(2)]\n\tif m == 1:\n\t\tprint(0)\n\telse:\n\t\ty1 = [0]\n\t\ty2 = [0]\n\t\tch = 0\n\t\tfor i in range(m):\n\t\t\ty1.append(l[0][i] + y1[i])\n\t\t\ty2.append(l[1][i] + y2[i])\n\t\tfor i in range(m):\n\t\t\tif i == m - 1:\n\t\t\t\tch = i\n\t\t\t\tbreak\n\t\t\tif y2[i + 1] > y1[m] - y1[i + 1]:\n\t\t\t\tch = i\n\t\t\t\tbreak\n\t\tprint(max(y1[m] - y1[ch + 1], y2[ch]))\n", "import sys\ninput = sys.stdin.readline\nt = []\nfor _ in range(int(input())):\n\tn = int(input())\n\ta = [int(i) for i in input().split()]\n\tb = [int(i) for i in input().split()]\n\t(res, u, d, up, do) = (float('inf'), 0, 0, [], [0])\n\tfor i in range(n):\n\t\tu += a[i]\n\t\td += b[i]\n\t\tup += [u]\n\t\tdo += [d]\n\tfor i in range(n):\n\t\tp1 = u - up[i]\n\t\tp2 = do[i]\n\t\tif p1 > p2:\n\t\t\tif p1 < res:\n\t\t\t\tres = p1\n\t\telif p2 < res:\n\t\t\tres = p2\n\tt += [res]\nfor k in t:\n\tprint(k)\n", "for _ in range(int(input())):\n\tm = int(input())\n\tliste1 = list(map(int, input().split()))\n\tliste2 = list(map(int, input().split()))\n\tlist1 = []\n\tlist2 = []\n\tliste1.reverse()\n\tlast = 0\n\tlast2 = 0\n\tlistefinale = []\n\tfor i in range(0, m - 1):\n\t\tlist1.append(liste1[i] + last)\n\t\tlist2.append(liste2[i] + last2)\n\t\tlast = last + liste1[i]\n\t\tlast2 = last2 + liste2[i]\n\tlist1.insert(0, 0)\n\tlist2.reverse()\n\tlist2.append(0)\n\tfor (elmt, elmtt) in zip(list1, list2):\n\t\tif elmt < elmtt:\n\t\t\tlistefinale.append(elmtt)\n\t\telse:\n\t\t\tlistefinale.append(elmt)\n\tlistefinale.sort()\n\tprint(listefinale[0])\n", "for _ in range(int(input())):\n\tm = int(input())\n\tup = list(map(int, input().split()))\n\tdown = list(map(int, input().split()))\n\tpref_up = [0]\n\tpref_down = [0]\n\tcount = 10 ** 10\n\tfor i in range(m):\n\t\tpref_up.append(pref_up[-1] + up[i])\n\t\tpref_down.append(pref_down[-1] + down[i])\n\tfor i in range(m):\n\t\tif max(pref_up[m] - pref_up[i + 1], pref_down[i]) < count:\n\t\t\tcount = max(pref_up[m] - pref_up[i + 1], pref_down[i])\n\tprint(count)\n", "t = int(input())\nwhile t > 0:\n\t(n, m) = (2, int(input()))\n\tA = [0] * n\n\tfor i in range(n):\n\t\ta1 = list(map(int, input().split()))\n\t\tA[i] = a1\n\tp = [0] * (m + 1)\n\tfor i in range(1, m + 1):\n\t\tp[i] = p[i - 1] + A[0][i - 1]\n\tp1 = [0] * (m + 1)\n\tfor i in range(1, m + 1):\n\t\tp1[i] = p1[i - 1] + A[1][i - 1]\n\tans = []\n\tfor i in range(m):\n\t\tx = p1[i] - p1[0]\n\t\ty = p[-1] - p[i + 1]\n\t\tans.append(max(x, y))\n\tprint(min(ans))\n\tt -= 1\n", "t = int(input())\nresults = [None] * t\nfor l in range(t):\n\tm = int(input())\n\trow_1 = [int(x) for x in input().split()]\n\trow_2 = [int(x) for x in input().split()]\n\tlowest_score = sum(row_1) + sum(row_2)\n\tscore1 = sum(row_1)\n\tscore2 = 0\n\tfor i in range(m):\n\t\tscore1 -= row_1[i]\n\t\tscore = max(score1, score2)\n\t\tif score < lowest_score:\n\t\t\tlowest_score = score\n\t\tscore2 += row_2[i]\n\tresults[l] = lowest_score\n[print(x) for x in results]\n", "test = int(input())\nwhile test:\n\ttest -= 1\n\tn = int(input())\n\tmat1 = list(map(int, input().split()))\n\tmat2 = list(map(int, input().split()))\n\tdp1 = [0 for i in range(n)]\n\tdp2 = [0 for i in range(n)]\n\talice = sum(mat1)\n\tfor i in range(n):\n\t\tdp1[i] = dp1[i - 1] + mat1[i]\n\tfor j in range(n):\n\t\tdp2[j] = dp2[j - 1] + mat2[j]\n\tmoney = 0\n\tscore = 10 ** 11\n\tfor i in range(n):\n\t\tmoney = max((dp2[i] - mat2[i]) % (10 ** 9 + 7), (alice - dp1[i]) % (10 ** 9 + 7))\n\t\tif score > money:\n\t\t\tscore = money % (10 ** 9 + 7)\n\tprint(score % (10 ** 9 + 7))\n", "from math import *\nfrom collections import defaultdict as dt\nfrom sys import stdin\ninp = lambda : stdin.readline().strip()\nI = lambda : int(inp())\nM = lambda : map(int, inp().split())\nL = lambda : list(M())\nmod = 1000000007\ninf = 100000000000000000000\nss = 'abcdefghijklmnopqrstuvwxyz'\n\ndef solve():\n\tn = I()\n\ta = L()\n\tb = L()\n\tif n == 1:\n\t\tprint(0)\n\t\treturn\n\tc = dt(int)\n\tc[n - 1] = a[-1]\n\td = dt(int)\n\td[0] = b[0]\n\te = inf\n\tfor i in range(n - 2, 0, -1):\n\t\tc[i] = a[i] + c[i + 1]\n\tfor i in range(1, n - 1):\n\t\td[i] = b[i] + d[i - 1]\n\tfor i in range(n):\n\t\te = min(e, max(c[i + 1], d[i - 1]))\n\tprint(e)\ntt = 1\ntt = I()\nfor _ in range(tt):\n\tsolve()\n", "import math\nimport sys\ninp = int(input())\nfor _ in range(inp):\n\tm = 2\n\tn = int(input())\n\tmat = []\n\trow1 = 0\n\trow2 = 0\n\tfor i in range(m):\n\t\ts = list(map(int, input().split(' ')))\n\t\tmat.append(s)\n\tres = float('inf')\n\tfor i in range(n):\n\t\trow1 += mat[0][i]\n\tfor i in range(n):\n\t\trow1 -= mat[0][i]\n\t\tres = min(res, max(row1, row2))\n\t\trow2 += mat[1][i]\n\tprint(res)\n", "import sys\ninput = sys.stdin.readline\nR = lambda : map(int, input().split())\nI = lambda : int(input())\nS = lambda : input().rstrip('\\n')\nL = lambda : list(R())\n\ndef solve():\n\tn = I()\n\ta = L()\n\tb = L()\n\tsuma = sum(a)\n\tsumb = sum(b)\n\tfor i in range(1, n):\n\t\ta[i] = a[i - 1] + a[i]\n\tfor i in range(n - 2, -1, -1):\n\t\tb[i] = b[i] + b[i + 1]\n\tans = 0\n\tl = []\n\tfor i in range(n):\n\t\tl.append(max(suma - a[i], sumb - b[i]))\n\tl.sort()\n\tprint(l[0])\nfor _ in range(I()):\n\tsolve()\n", "import collections as cc\nimport bisect as bi\nimport heapq as hp\nimport math as mt\nimport itertools as it\nimport sys\nimport io, os\ninput = sys.stdin.readline\nI = lambda : list(map(int, input().split()))\nfor tc in range(int(input())):\n\t(n,) = I()\n\tar = [I() for i in range(2)]\n\tsuff = ar[0].copy()\n\tfor i in range(n - 2, -1, -1):\n\t\tsuff[i] += suff[i + 1]\n\tpref = ar[1].copy()\n\tfor i in range(1, n):\n\t\tpref[i] += pref[i - 1]\n\ttemp = []\n\tsuff = suff[1:] + [0]\n\tpref = [0] + pref\n\tfor i in range(n):\n\t\ttemp.append(max(suff[i], pref[i]))\n\tprint(min(temp))\n", "import math\nimport sys\nfor _ in range(int(input())):\n\tm = int(input())\n\tc1 = list(map(int, input().split()))\n\tc2 = list(map(int, input().split()))\n\tmin_ = sys.maxsize\n\ttemp = 0\n\tresult = 0\n\tsum1 = sum(c1)\n\tsum2 = 0\n\tfor i in range(m):\n\t\tif i == 0:\n\t\t\tsum2 = 0\n\t\telse:\n\t\t\tsum2 += c2[i - 1]\n\t\tsum1 -= c1[i]\n\t\tscore_bob = max(sum1, sum2)\n\t\tif score_bob < min_:\n\t\t\tmin_ = score_bob\n\t\t\tresult = score_bob\n\t\t\ttemp = i\n\tprint(result)\n", "test = int(input())\nfor t in range(test):\n\tm = int(input())\n\ta = []\n\ta.append(list(map(int, input().split())))\n\ta.append(list(map(int, input().split())))\n\tif m == 1:\n\t\tprint(0)\n\t\tcontinue\n\tfor i in range(1, m):\n\t\ta[0][i] += a[0][i - 1]\n\tfor i in range(m - 2, -1, -1):\n\t\ta[1][i] += a[1][i + 1]\n\tbob = min(a[0][m - 1] - a[0][0], a[1][0] - a[1][m - 1])\n\tfor i in range(1, m - 1):\n\t\tbob = min(bob, max(a[0][m - 1] - a[0][i], a[1][0] - a[1][i]))\n\tprint(bob)\n", "def main():\n\tfor _ in range(int(input())):\n\t\tm = int(input())\n\t\tL1 = [int(l) for l in input().split()]\n\t\tL2 = [int(l) for l in input().split()]\n\t\tpr1 = [0]\n\t\tpr2 = [0]\n\t\tsm = 0\n\t\tfor i in range(m):\n\t\t\tsm += L1[i] + L2[i]\n\t\t\tpr1.append(pr1[-1] + L1[i])\n\t\t\tpr2.append(pr2[-1] + L2[i])\n\t\tr2 = 10000000000.0\n\t\tfor i in range(1, m):\n\t\t\tr2 = min(r2, max(pr2[i - 1] - pr2[0], pr1[-1] - pr1[i]))\n\t\tr2 = min(r2, pr2[-2])\n\t\tprint(r2)\nmain()\n", "def coin_rows(matrix):\n\tn = len(matrix[0])\n\tif n == 1:\n\t\treturn 0\n\tsums1 = [0] * n\n\tsums1[0] = matrix[0][0]\n\tfor i in range(1, n):\n\t\tsums1[i] = matrix[0][i] + sums1[i - 1]\n\tsums2 = [0] * n\n\tsums2[0] = matrix[1][0]\n\tfor i in range(1, n):\n\t\tsums2[i] = matrix[1][i] + sums2[i - 1]\n\tscore = sums1[n - 1] - sums1[0]\n\tfor i in range(1, n):\n\t\tscore = min(max(sums1[n - 1] - sums1[i], sums2[i - 1]), score)\n\treturn score\nT = int(input())\nfor t in range(T):\n\tn = int(input())\n\tmatrix = []\n\tfor i in range(2):\n\t\trow = list(map(int, input().split()))\n\t\tmatrix.append(row)\n\tprint(coin_rows(matrix))\n", "def score(m, l1, l2):\n\tmat = [l1, l2]\n\tsum1 = sum(l1)\n\ts4 = sum(l2)\n\tsum2 = 0\n\tsum1 -= l1[0]\n\tsum2 += mat[1][0]\n\tfor i in range(1, m):\n\t\tif sum2 > sum1:\n\t\t\ts4 -= mat[1][i - 1]\n\t\telse:\n\t\t\tsum1 -= mat[0][i]\n\t\t\tsum2 += mat[1][i]\n\ts4 -= mat[1][m - 1]\n\treturn max(sum1, s4)\nfor i in range(int(input())):\n\tm = int(input())\n\tl1 = list(map(int, input().split()))\n\tl2 = list(map(int, input().split()))\n\tprint(score(m, l1, l2))\n", "for _ in range(int(input())):\n\tm = int(input())\n\tar = list(map(int, input().split()))\n\tbr = list(map(int, input().split()))\n\tr0 = sum(ar)\n\tr1 = sum(br)\n\tsu = 0\n\tfor i in range(m):\n\t\tsu += ar[i]\n\t\tar[i] = su\n\tsu = 0\n\tfor i in range(m - 1, -1, -1):\n\t\tsu += br[i]\n\t\tbr[i] = su\n\tans = []\n\tfor i in range(m):\n\t\tx1 = r0 - ar[i]\n\t\tx2 = r1 - br[i]\n\t\tans.append(max(x1, x2))\n\tprint(min(ans))\n", "import sys\ninput = sys.stdin.readline\nt = int(input())\nwhile t > 0:\n\tm = int(input())\n\ta = [*map(int, input().split())]\n\tb = [*map(int, input().split())]\n\ts = sum(a) - a[0]\n\tans = s\n\tx = 0\n\tfor i in range(1, m):\n\t\tx += b[i - 1]\n\t\ts -= a[i]\n\t\tp = max(x, s)\n\t\tans = min(ans, p)\n\tprint(ans)\n\tt -= 1\n", "t = int(input())\nfor _ in range(t):\n\tn = int(input())\n\tgame_up = list(map(int, input().split()))\n\tgame_down = list(map(int, input().split()))\n\tsum_up = sum(game_up)\n\tsum_down = 0\n\tbob_min = 10 ** 10 + 2\n\tfor i in range(n):\n\t\tsum_up -= game_up[i]\n\t\tbob_min = min(bob_min, max(sum_up, sum_down))\n\t\tsum_down += game_down[i]\n\tprint(bob_min)\n", "t = int(input())\nfor _ in range(t):\n\tf = int(input())\n\tif f == 1:\n\t\ta = int(input())\n\t\tb = int(input())\n\t\tprint('0')\n\telse:\n\t\ta = list(map(int, input().split()))\n\t\tb = list(map(int, input().split()))\n\t\tsa = 0\n\t\tsb = 0\n\t\tsua = []\n\t\tsub = []\n\t\tfor i in range(f):\n\t\t\tsa = sa + a[f - 1 - i]\n\t\t\tsb = sb + b[i]\n\t\t\tsub.append(sb)\n\t\t\tsua.insert(0, sa)\n\t\tsua.append(0)\n\t\tsub.insert(0, 0)\n\t\tflag = 0\n\t\tfor i in range(f + 1):\n\t\t\tif sua[i] <= sub[i]:\n\t\t\t\tbreak\n\t\tk = i\n\t\tif i == 0:\n\t\t\tprint(sua[1])\n\t\telif i == f:\n\t\t\tprint(sub[-2])\n\t\telse:\n\t\t\tprint(max(min(sua[k], sub[k]), sub[k - 1]))\n", "for ii in range(int(input())):\n\tn = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\t(u, d, co) = (0, sum(a), 10 ** 9)\n\tfor jj in range(n):\n\t\td -= a[jj]\n\t\tco = min(co, max(u, d))\n\t\tu += b[jj]\n\tprint(co)\n", "import sys\nfrom sys import stdin, stdout\nfrom math import ceil, floor, sqrt, log, log2, log10\nfrom collections import Counter\nint_max = float('inf')\nint_min = -float('inf')\nANS = []\ninput = stdin.readline\n\ndef solve():\n\tpass\nt = int(input())\nfor i in range(t):\n\tn = int(input())\n\tarr = list(map(int, input().split()))\n\tbrr = list(map(int, input().split()))\n\tif n == 1:\n\t\tprint(0)\n\t\tcontinue\n\tsuff = [0]\n\tfor i in range(n - 1, -1, -1):\n\t\tsuff.append(suff[-1] + arr[i])\n\tpref = [0]\n\tfor i in range(n):\n\t\tpref.append(pref[-1] + brr[i])\n\tans = int_max\n\ti = 0\n\tj = n - 1\n\twhile i < n:\n\t\tans = min(ans, max(suff[i], pref[j]))\n\t\ti += 1\n\t\tj -= 1\n\tprint(ans)\nprint('\\n'.join(ANS))\n", "T = int(input())\nfor _ in range(T):\n\tm = int(input())\n\tcoins = []\n\tcoins.append(list(map(int, input().split())))\n\tcoins.append(list(map(int, input().split())))\n\tbob = float('inf')\n\tsumTop = sum(coins[0]) - coins[0][0]\n\tsumBot = 0\n\tbob = min(max(sumTop, sumBot), bob)\n\tfor i in range(1, m):\n\t\tsumTop -= coins[0][i]\n\t\tsumBot += coins[1][i - 1]\n\t\tbob = min(max(sumTop, sumBot), bob)\n\tprint(0 if m == 1 else bob)\n", "t = int(input())\nfor case in range(t):\n\tm = int(input())\n\ta = []\n\tb = []\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tpfa = [0]\n\tpfb = [0]\n\tfor x in a:\n\t\tpfa.append(x + pfa[-1])\n\tfor x in b:\n\t\tpfb.append(x + pfb[-1])\n\tbest = 100000000000\n\tfor i in range(1, m + 1):\n\t\tbest = min(best, max(pfb[i - 1], pfa[-1] - pfa[i]))\n\tprint(best)\n", "for _ in range(int(input())):\n\tm = int(input())\n\ta1 = list(map(int, input().split()))\n\ta2 = list(map(int, input().split()))\n\t(ac1, ac2) = (0, 0)\n\t(x, y) = (0, m - 1)\n\twhile x != y:\n\t\tif ac1 + a2[x] <= ac2 + a1[y]:\n\t\t\tac1 += a2[x]\n\t\t\tx += 1\n\t\telse:\n\t\t\tac2 += a1[y]\n\t\t\ty -= 1\n\tprint(max(ac1, ac2))\n", "t = int(input())\nfor _ in range(t):\n\tm = int(input())\n\tfirst = list(map(int, input().split()))\n\tsecond = list(map(int, input().split()))\n\tfirst_sum = sum(first)\n\tleft_abandoned = 0\n\tright_abandoned = first_sum - first[0]\n\talice_best = right_abandoned\n\ti = 0\n\twhile True:\n\t\tbob_best = max(left_abandoned, right_abandoned)\n\t\talice_best = min(alice_best, bob_best)\n\t\tif i >= len(first) - 1:\n\t\t\tbreak\n\t\tleft_abandoned += second[i]\n\t\tright_abandoned -= first[i + 1]\n\t\ti += 1\n\tprint(alice_best)\n", "t = int(input())\nfor _ in range(t):\n\tm = int(input())\n\tl1 = list(map(int, input().split()))\n\tl2 = list(map(int, input().split()))\n\tk1 = l1[:]\n\tk2 = l2[:]\n\tmi = 100000000000.0\n\tif m == 1:\n\t\tprint(0)\n\telif m == 2:\n\t\tprint(min(l1[1], l2[0]))\n\telse:\n\t\tfor i in range(1, m):\n\t\t\tk2[i] += k2[i - 1]\n\t\tfor i in range(m - 2, -1, -1):\n\t\t\tk1[i] += k1[i + 1]\n\t\tfor i in range(1, m - 1):\n\t\t\tmi = min(mi, max(k1[i + 1], k2[i - 1]))\n\t\tmi = min(mi, k1[1])\n\t\tmi = min(mi, k2[m - 2])\n\t\tprint(mi)\n", "t = int(input())\nfor tc in range(t):\n\tn = int(input())\n\ta = []\n\tfor i in range(2):\n\t\tb = list(map(int, input().split()))\n\t\ta.append(b)\n\tfor i in range(2):\n\t\tfor j in range(1, n):\n\t\t\tif i == 0:\n\t\t\t\ta[i][j] = a[i][j] + a[i][j - 1]\n\t\t\telse:\n\t\t\t\ta[i][j] = a[i][j] + a[i][j - 1]\n\tbest = float('inf')\n\tfor j in range(n):\n\t\tif j == 0:\n\t\t\tbob = a[0][-1] - a[0][0]\n\t\telif j == n - 1:\n\t\t\tbob = a[1][j - 1]\n\t\telse:\n\t\t\tbob = max(a[0][-1] - a[0][j], a[1][j - 1])\n\t\tif best > bob:\n\t\t\tbest = bob\n\tprint(best)\n", "import sys\nfrom collections import Counter\n\ndef get_ints():\n\treturn list(map(int, sys.stdin.readline().strip().split()))\nsys.setrecursionlimit(20000)\nT = int(input())\nfor _ in range(T):\n\tm = int(input())\n\tA1 = get_ints()\n\tA2 = get_ints()\n\tA1_sum = sum(A1) - A1[0]\n\tA2_sum = 0\n\tmin_score = max(A1_sum, A2_sum)\n\tfor i in range(1, m):\n\t\tA1_sum -= A1[i]\n\t\tA2_sum += A2[i - 1]\n\t\tscore = max(A1_sum, A2_sum)\n\t\tif score < min_score:\n\t\t\tmin_score = score\n\tprint(min_score)\n", "import math\n\ndef solve():\n\tm = int(input())\n\tmat = []\n\tfor i in range(2):\n\t\tmat.append(list(map(int, input().split())))\n\tprefix1 = [0 for i in range(m)]\n\tprefix2 = [0 for j in range(m)]\n\trow1 = mat[0][0]\n\tprefix1[0] = mat[0][0]\n\trow2 = mat[1][0]\n\tprefix2[0] = mat[1][0]\n\tfor i in range(1, m):\n\t\tprefix1[i] = prefix1[i - 1] + mat[0][i]\n\t\tprefix2[i] = prefix2[i - 1] + mat[1][i]\n\t\trow1 += mat[0][i]\n\t\trow2 += mat[1][i]\n\tans = 10 ** 15\n\tfor i in range(m):\n\t\ttemp1 = 0\n\t\tif i != 0:\n\t\t\ttemp1 = prefix2[i - 1]\n\t\ttemp2 = row1 - prefix1[i]\n\t\tans = min(ans, max(temp1, temp2))\n\treturn ans\nt = int(input())\nfor i in range(t):\n\tprint(solve())\n", "t = int(input())\n\ndef solve():\n\tm = int(input())\n\tarr1 = list(map(int, input().split()))\n\tarr2 = list(map(int, input().split()))\n\tif m == 1:\n\t\tprint(0)\n\t\treturn\n\tps1 = [arr1[0]]\n\tfor i in range(1, m):\n\t\tps1.append(ps1[-1] + arr1[i])\n\tps2 = [0] * m\n\tps2[-1] = arr2[-1]\n\tfor i in reversed(range(m - 1)):\n\t\tps2[i] = ps2[i + 1] + arr2[i]\n\tans = []\n\tfor i in range(m):\n\t\tbob = []\n\t\tif i < m - 1:\n\t\t\tbob.append(ps1[-1] - ps1[i])\n\t\tif i > 0:\n\t\t\tbob.append(ps2[0] - ps2[i])\n\t\tans.append(max(bob))\n\tprint(min(ans))\nfor i in range(t):\n\tsolve()\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nfrom collections import Counter, defaultdict\nimport math\nimport heapq\nimport bisect\n\ndef nck(n, k):\n\tres = 1\n\tfor i in range(1, k + 1):\n\t\tres = res * (n - i + 1) // i\n\treturn res\nfor _ in range(int(input())):\n\tn = int(input())\n\ta1 = list(map(int, input().split()))\n\ta2 = list(map(int, input().split()))\n\tfor i in range(1, n):\n\t\ta2[i] += a2[i - 1]\n\tfor i in range(1, n):\n\t\ta1[i] += a1[i - 1]\n\ta = 0\n\tb = 10 ** 20\n\tfor i in range(n):\n\t\ts2 = a1[i]\n\t\tif i == 0:\n\t\t\ts2 += a2[-1]\n\t\telse:\n\t\t\ts2 += a2[-1] - a2[i - 1]\n\t\tvv = 0\n\t\tv1 = 0\n\t\tif i > 0:\n\t\t\tv1 += a2[i - 1]\n\t\tvv += a1[-1] - a1[i]\n\t\tb = min(b, max(vv, v1))\n\tprint(b)\n", "for i in range(int(input())):\n\tm = int(input())\n\ta1 = list(map(int, input().split()))\n\ta2 = list(map(int, input().split()))\n\ttop = sum(a1) - a1[0]\n\tbot = 0\n\tans = 999999999999\n\tfor i in range(m - 1):\n\t\tans = min(ans, max(top, bot))\n\t\tbot += a2[i]\n\t\ttop -= a1[i + 1]\n\tans = min(ans, bot)\n\tprint(ans)\n", "from itertools import accumulate\n\ndef solve():\n\tm = int(input())\n\ta1 = [int(i) for i in input().split()]\n\ta2 = [int(i) for i in input().split()]\n\tacc1 = list(accumulate(a1))\n\tacc2 = list(accumulate(a2))\n\tans = 1 << 32\n\tfor i in range(m):\n\t\tres1 = 0\n\t\tres2 = 0\n\t\tif i > 0:\n\t\t\tres2 = acc2[i - 1]\n\t\tif i < m - 1:\n\t\t\tres1 = acc1[m - 1] - acc1[i]\n\t\tans = min(ans, max(res1, res2))\n\treturn ans\nt = int(input())\nfor ind in range(t):\n\tprint(solve())\n", "import sys\ninput = sys.stdin.readline\nt = int(input())\nfor test in range(t):\n\tm = int(input())\n\trad1 = list(map(int, input().split()))\n\trad2 = list(map(int, input().split()))\n\tsteps1 = m - 1\n\tsteps2 = 0\n\tcoins1 = 0\n\tcoins2 = 0\n\twhile steps1 != steps2:\n\t\tif coins1 + rad1[steps1] < coins2 + rad2[steps2]:\n\t\t\tcoins1 = coins1 + rad1[steps1]\n\t\t\tsteps1 = steps1 - 1\n\t\telse:\n\t\t\tcoins2 = coins2 + rad2[steps2]\n\t\t\tsteps2 = steps2 + 1\n\tprint(max(coins1, coins2))\n", "from __future__ import division, print_function\nfrom math import inf\nimport itertools\nimport sys\nif sys.version_info[0] < 3:\n\tinput = raw_input\n\trange = xrange\n\tfilter = itertools.ifilter\n\tmap = itertools.imap\n\tzip = itertools.izip\nread_int_vec = lambda x: [int(c) for c in x.split(' ')]\n\ndef solution(A):\n\tm = len(A[0])\n\tF1 = [0]\n\tF2 = [0]\n\tfor i in range(m):\n\t\tF1.append(F1[-1] + A[0][i])\n\t\tF2.append(F2[-1] + A[1][i])\n\tans = F2[m]\n\tfor i in range(m):\n\t\tS2 = F1[m] - F1[i + 1]\n\t\tS3 = F2[i]\n\t\tans = min(ans, max(S3, S2))\n\treturn ans\n\ndef test(A):\n\tprint(solution(A))\nn_tests = int(input())\nread_int_vec = lambda x: [int(c) for c in x.split(' ')]\nfor _ in range(n_tests):\n\tm = int(input())\n\tA = []\n\tfor i in range(2):\n\t\tl = read_int_vec(input())\n\t\tA.append(l)\n\tprint(solution(A))\n", "def solve():\n\tt = int(input())\n\tfor _ in range(t):\n\t\tm = int(input())\n\t\tmatrix = [list(map(int, input().split())), list(map(int, input().split()))]\n\t\tscore = [sum(matrix[0]) - matrix[0][0]]\n\t\t(up, down) = (score[0], 0)\n\t\tfor i in range(1, m):\n\t\t\tup -= matrix[0][i]\n\t\t\tdown += matrix[1][i - 1]\n\t\t\tscore.append(max(up, down))\n\t\tprint(min(score))\nsolve()\n", "from os import path\nfrom io import BytesIO, IOBase\nimport sys\nfrom heapq import heappush, heappop\nfrom functools import cmp_to_key as ctk\nfrom collections import deque, Counter, defaultdict as dd\nfrom bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right\nfrom itertools import permutations\nfrom datetime import datetime\nfrom math import ceil, sqrt, log, gcd\n\ndef ii():\n\treturn int(input())\n\ndef si():\n\treturn input().rstrip()\n\ndef mi():\n\treturn map(int, input().split())\n\ndef li():\n\treturn list(mi())\nabc = 'abcdefghijklmnopqrstuvwxyz'\nmod = 1000000007\ninf = float('inf')\nvow = ['a', 'e', 'i', 'o', 'u']\n(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])\n\ndef bo(i):\n\treturn ord(i) - ord('0')\nfile = 1\n\ndef ceil(a, b):\n\treturn (a + b - 1) // b\n\ndef solve():\n\tfor _ in range(1, ii() + 1):\n\t\tm = ii()\n\t\ta = li()\n\t\tb = li()\n\t\tpre = [[0, 0] for i in range(m)]\n\t\tfor i in range(m):\n\t\t\tif i:\n\t\t\t\tpre[i][0] += pre[i - 1][0]\n\t\t\tpre[i][0] += a[i]\n\t\tfor i in range(m):\n\t\t\tif i:\n\t\t\t\tpre[i][1] += pre[i - 1][1]\n\t\t\tpre[i][1] += b[i]\n\t\tmnx = inf\n\t\tfor i in range(m):\n\t\t\tr = pre[-1][0] - pre[i][0]\n\t\t\td = 0\n\t\t\tif i:\n\t\t\t\td = pre[i - 1][1]\n\t\t\tmnx = min(mnx, max(r, d))\n\t\tif mnx == inf:\n\t\t\tmnx = 0\n\t\tprint(mnx)\nif file:\n\tif path.exists('input.txt'):\n\t\tsys.stdin = open('input.txt', 'r')\n\t\tsys.stdout = open('output.txt', 'w')\n\telse:\n\t\tinput = sys.stdin.readline\nsolve()\n", "from sys import stdin, stdout\nt = int(stdin.readline())\nfor _ in range(t):\n\tm = int(stdin.readline())\n\ta1 = [int(x) for x in stdin.readline().split()]\n\ta2 = [int(x) for x in stdin.readline().split()]\n\ttop = sum(a1) - a1[0]\n\tbottom = 0\n\tanswer = top\n\tfor i in range(m - 1):\n\t\ttop -= a1[i + 1]\n\t\tbottom += a2[i]\n\t\tanswer = min(answer, max(top, bottom))\n\tstdout.write(str(answer) + '\\n')\n", "def solve(upper, lower, n):\n\tsum_upper = [0] * n\n\tsum_lower = [0] * n\n\tupper_row = 0\n\tlower_row = 0\n\tfor x in range(n):\n\t\tupper_row += upper[x]\n\t\tlower_row += lower[x]\n\t\tsum_upper[x] = upper_row\n\t\tsum_lower[x] = lower_row\n\talice = [0] * n\n\tbob = [0] * n\n\talice[0] = upper[0] + lower_row\n\tbob[0] = upper_row - upper[0]\n\tresult = bob[0]\n\tfor x in range(1, n):\n\t\talice[x] = alice[x - 1] + upper[x] - lower[x - 1]\n\t\tbob[x] = max(sum_upper[n - 1] - sum_upper[x], sum_lower[x - 1])\n\t\tif bob[x] <= result:\n\t\t\tresult = bob[x]\n\tprint(result)\nfor _ in range(int(input())):\n\tn = int(input())\n\tsolve(list(map(int, input().split())), list(map(int, input().split())), n)\n", "for _ in range(int(input())):\n\tm = int(input())\n\tarr = [list(map(int, input().split())), list(map(int, input().split()))]\n\tprefix1 = [0]\n\tfor num in arr[0]:\n\t\tprefix1.append(prefix1[-1] + num)\n\tprefix2 = [0]\n\tfor num in arr[1]:\n\t\tprefix2.append(prefix2[-1] + num)\n\tans = float('inf')\n\tfor i in range(1, m + 1):\n\t\tans = min(ans, max(prefix1[m] - prefix1[i], prefix2[i - 1]))\n\tprint(ans)\n", "import sys\ninput = sys.stdin.readline\nfor _ in range(int(input())):\n\tm = int(input())\n\ti1 = list(map(int, input().split()))\n\ti2 = list(map(int, input().split()))\n\tsu1 = sum(i1)\n\tsu2 = sum(i2)\n\tres = []\n\tresd1 = 0\n\tresd2 = su2\n\tfor i in range(m):\n\t\tresd1 += i1[i]\n\t\tres.append(max(su1 - resd1, su2 - resd2))\n\t\tresd2 -= i2[i]\n\tprint(min(res))\n", "import sys\nMOD = 1000000007\n\ndef inp():\n\treturn sys.stdin.readline().strip()\n\ndef ii():\n\treturn int(inp())\n\ndef iis():\n\treturn [int(i) for i in inp().split()]\n\ndef solve():\n\tm = ii()\n\ta1 = iis()\n\ta2 = iis()\n\ta1pre = [a1[0]]\n\ta2pre = [a2[0]]\n\tfor i in range(1, m):\n\t\ta1pre.append(a1pre[-1] + a1[i])\n\t\ta2pre.append(a2pre[-1] + a2[i])\n\tans = MOD\n\tans = min(ans, a1pre[-1] - a1pre[0])\n\tfor i in range(1, m):\n\t\tans = min(ans, max(a2pre[i - 1], a1pre[-1] - a1pre[i]))\n\treturn ans\nt = ii()\nfor _ in range(t):\n\tprint(solve())\n", "n = int(input())\nfor i in range(n):\n\tl1 = []\n\tl2 = []\n\tm = int(input())\n\tg1 = input()\n\tg1 = g1.split()\n\tg2 = input()\n\tg2 = g2.split()\n\tfor o in g1:\n\t\tl1.append(int(o))\n\tfor o in g2:\n\t\tl2.append(int(o))\n\ts = sum(l1)\n\tz1 = sum(l1) - l1[0]\n\tz2 = 0\n\tzaehler = -1\n\tspeicher = 1000000000\n\tspeicher2 = 1000000000\n\tfor x in range(len(l1) - 1):\n\t\tz1 -= l1[x + 1]\n\t\tz2 += l2[x]\n\t\tif max(z1, z2) < speicher:\n\t\t\tspeicher = max(z1, z2)\n\t\tif max(z1, z2) > speicher2:\n\t\t\tbreak\n\t\tspeicher2 = speicher\n\tif speicher == 1000000000:\n\t\tspeicher = 0\n\telif speicher > sum(l1) - l1[0]:\n\t\tspeicher = sum(l1) - l1[0]\n\tprint(speicher)\n", "from itertools import accumulate\nfrom sys import stdin, gettrace\nif gettrace():\n\n\tdef inputi():\n\t\treturn input()\nelse:\n\n\tdef input():\n\t\treturn next(stdin)[:-1]\n\n\tdef inputi():\n\t\treturn stdin.buffer.readline()\n\ndef solve():\n\tm = int(input())\n\taa1 = [int(a) for a in input().split()]\n\taa2 = [int(a) for a in input().split()]\n\tacc1 = list(accumulate(aa1))\n\tacc2 = [0] + list(accumulate(aa2))\n\tres = min((max(acc2[i], acc1[-1] - acc1[i]) for i in range(m)))\n\tprint(res)\n\ndef main():\n\tt = int(input())\n\tfor _ in range(t):\n\t\tsolve()\nmain()\n", "import os, sys\nfrom io import BytesIO, IOBase\n\ndef main():\n\tfor _ in range(int(input())):\n\t\tn = int(input())\n\t\ta = [[0] + list(map(int, input().split())) for _ in range(2)]\n\t\tfor i in range(2):\n\t\t\tfor j in range(1, n + 1):\n\t\t\t\ta[i][j] += a[i][j - 1]\n\t\tprint(min((max(a[0][n] - a[0][i], a[1][i - 1]) for i in range(1, n + 1))))\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nmain()\n", "t = int(input())\nfor i in range(t):\n\tm = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tpr1 = [0] * m\n\tpr2 = [0] * m\n\tpr1[0] = a[0]\n\tpr2[0] = b[0]\n\tfor j in range(1, m):\n\t\tpr1[j] = pr1[j - 1] + a[j]\n\t\tpr2[j] = pr2[j - 1] + b[j]\n\tpos = 0\n\tans = pr1[-1] - pr1[0]\n\tfor j in range(1, m):\n\t\tans = min(ans, max(pr1[-1] - pr1[j], pr2[j - 1]))\n\tprint(ans)\n", "import sys, math\n\ndef get_ints():\n\treturn map(int, sys.stdin.readline().strip().split())\n\ndef get_ls():\n\treturn list(map(int, sys.stdin.readline().strip().split()))\n\ndef main():\n\tfor _ in range(int(input())):\n\t\tn = int(input())\n\t\tls = []\n\t\tfor i in range(2):\n\t\t\tx = get_ls()\n\t\t\tls.append(x)\n\t\tsum1 = sum(ls[0])\n\t\tsum2 = 0\n\t\tans = math.inf\n\t\tfor i in range(n):\n\t\t\tsum1 -= ls[0][i]\n\t\t\tans = min(ans, max(sum1, sum2))\n\t\t\tsum2 += ls[1][i]\n\t\tprint(ans)\nmain()\n", "def inp():\n\treturn int(input())\n\ndef invr():\n\treturn list(map(int, input().split()))\n\ndef score(matrix):\n\tfirst_row_sum = sum(matrix[0])\n\tsecond_row_sum = 0\n\tmax_score = float('inf')\n\tfor i in range(len(matrix[0])):\n\t\tsum_one = first_row_sum - matrix[0][i]\n\t\tif first_row_sum - matrix[0][i] != 0:\n\t\t\tfirst_row_sum -= matrix[0][i]\n\t\tsum_two = second_row_sum\n\t\tsecond_row_sum += matrix[1][i]\n\t\tmax_score = min(max_score, max(sum_one, sum_two))\n\tprint(max_score)\nn = inp()\nmatrices = []\nfor i in range(n):\n\tm = inp()\n\ttmp = []\n\tfor _ in range(2):\n\t\tline = invr()\n\t\ttmp.append(line)\n\tmatrices.append(tmp)\nfor matrix in matrices:\n\tscore(matrix)\n", "import sys\nimport math\nimport random\nfrom queue import PriorityQueue as PQ\nfrom bisect import bisect_left as BSL\nfrom bisect import bisect_right as BSR\nfrom collections import OrderedDict as OD\nfrom collections import Counter\nfrom itertools import permutations\nmod = 1000000007\ntry:\n\tsys.stdin = open('actext.txt', 'r')\n\tOPENFILE = 1\nexcept:\n\tpass\n\ndef get_ints():\n\treturn map(int, input().split())\n\ndef palindrome(s):\n\tmid = len(s) // 2\n\tfor i in range(mid):\n\t\tif s[i] != s[len(s) - i - 1]:\n\t\t\treturn False\n\treturn True\n\ndef check(i, n):\n\tif 0 <= i < n:\n\t\treturn True\n\telse:\n\t\treturn False\nt = int(input())\nfor tt in range(t):\n\tm = int(input())\n\tarr = []\n\tfor i in range(2):\n\t\tarr.append(list(map(int, input().split())))\n\tif m == 1:\n\t\tprint(0)\n\telse:\n\t\tsumarr = [[], []]\n\t\tsm1 = 0\n\t\tsm2 = 0\n\t\tfor i in range(m - 1, -1, -1):\n\t\t\tsm1 += arr[0][i]\n\t\t\tsumarr[0].insert(0, sm1)\n\t\tfor i in range(m):\n\t\t\tsm2 += arr[1][i]\n\t\t\tsumarr[1].append(sm2)\n\t\tans = sum(sumarr[0]) + sum(sumarr[1])\n\t\tfor i in range(0, m - 1):\n\t\t\ttemp = max(sumarr[0][i] - arr[0][i], sumarr[1][i] - arr[1][i])\n\t\t\tans = min(ans, temp)\n\t\tans = min(ans, sumarr[1][m - 2])\n\t\tprint(ans)\n", "for _ in range(int(input())):\n\tm = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\ts = sum(b)\n\tsa = sum(a)\n\tpref_a = [a[0]]\n\tpref_b = [b[0]]\n\tfor i in range(1, m):\n\t\tpref_a.append(pref_a[i - 1] + a[i])\n\t\tpref_b.append(pref_b[i - 1] + b[i])\n\tel = 0\n\twhile pref_b[el] < sa - pref_a[el]:\n\t\tel += 1\n\t\tif el >= m - 1:\n\t\t\tel = m - 1\n\t\t\tbreak\n\tif el == 0:\n\t\tprint(sa - a[0])\n\telse:\n\t\tprint(max(sa - pref_a[el], pref_b[el - 1]))\n"]

difficulty: EASY

source: codeforces

raw_problem:
C. Coin Rows

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Alice and Bob are playing a game on a matrix, consisting of $$$2$$$ rows and $$$m$$$ columns. The cell in the $$$i$$$-th row in the $$$j$$$-th column contains $$$a_{i, j}$$$ coins in it.

Initially, both Alice and Bob are standing in a cell $$$(1, 1)$$$. They are going to perform a sequence of moves to reach a cell $$$(2, m)$$$.

The possible moves are:

 Move right — from some cell $$$(x, y)$$$ to $$$(x, y + 1)$$$;

 Move down — from some cell $$$(x, y)$$$ to $$$(x + 1, y)$$$.

First, Alice makes all her moves until she reaches $$$(2, m)$$$. She collects the coins in all cells she visit (including the starting cell).

When Alice finishes, Bob starts his journey. He also performs the moves to reach $$$(2, m)$$$ and collects the coins in all cells that he visited, but Alice didn't.

The score of the game is the total number of coins Bob collects.

Alice wants to minimize the score. Bob wants to maximize the score. What will the score of the game be if both players play optimally?

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

Then the descriptions of $$$t$$$ testcases follow.

The first line of the testcase contains a single integer $$$m$$$ ($$$1 \le m \le 10^5$$$) — the number of columns of the matrix.

The $$$i$$$-th of the next $$$2$$$ lines contain $$$m$$$ integers $$$a_{i,1}, a_{i,2}, \dots, a_{i,m}$$$ ($$$1 \le a_{i,j} \le 10^4$$$) — the number of coins in the cell in the $$$i$$$-th row in the $$$j$$$-th column of the matrix.

The sum of $$$m$$$ over all testcases doesn't exceed $$$10^5$$$.

Output

For each testcase print a single integer — the score of the game if both players play optimally.

Example

Input

3
3
1 3 7
3 5 1
3
1 3 9
3 5 1
1
4
7

Output

7
8
0

Note

The paths for the testcases are shown on the following pictures. Alice's path is depicted in red and Bob's path is depicted in blue.

question:
Alice and Bob are playing a game on a matrix, consisting of $$$2$$$ rows and $$$m$$$ columns. The cell in the $$$i$$$-th row in the $$$j$$$-th column contains $$$a_{i, j}$$$ coins in it.
Initially, both Alice and Bob are standing in a cell $$$(1, 1)$$$. They are going to perform a sequence of moves to reach a cell $$$(2, m)$$$.
The possible moves are:
 -  Move right — from some cell $$$(x, y)$$$ to $$$(x, y + 1)$$$; -  Move down — from some cell $$$(x, y)$$$ to $$$(x + 1, y)$$$. First, Alice makes all her moves until she reaches $$$(2, m)$$$. She collects the coins in all cells she visit (including the starting cell).
When Alice finishes, Bob starts his journey. He also performs the moves to reach $$$(2, m)$$$ and collects the coins in all cells that he visited, but Alice didn't.
The score of the game is the total number of coins Bob collects.
Alice wants to minimize the score. Bob wants to maximize the score. What will the score of the game be if both players play optimally?

Input
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.
Then the descriptions of $$$t$$$ testcases follow.
The first line of the testcase contains a single integer $$$m$$$ ($$$1 \le m \le 10^5$$$) — the number of columns of the matrix.
The $$$i$$$-th of the next $$$2$$$ lines contain $$$m$$$ integers $$$a_{i,1}, a_{i,2}, \dots, a_{i,m}$$$ ($$$1 \le a_{i,j} \le 10^4$$$) — the number of coins in the cell in the $$$i$$$-th row in the $$$j$$$-th column of the matrix.
The sum of $$$m$$$ over all testcases doesn't exceed $$$10^5$$$.

Output
For each testcase print a single integer — the score of the game if both players play optimally.

Example
Input
3
3
1 3 7
3 5 1
3
1 3 9
3 5 1
1
4
7

Output
7
8
0

Note
The paths for the testcases are shown on the following pictures. Alice's path is depicted in red and Bob's path is depicted in blue.
 ![image](1.png)

tags: ['Dynamic programming', 'Complete search', 'Implementation', 'Constructive algorithms']

skill_types: ['Dynamic programming', 'Complete search']

raw_tags: ['implementation', 'brute force', 'dp', 'constructive algorithms']

data_split: test