F. Triangular Paths

problem_index: F

time_limit: 2 seconds

memory_limit: 256 megabytes

solutions: ["import os\nimport math\ntrue = True\nfalse = False\nfrom collections import defaultdict, deque, Counter\nfrom functools import reduce\nfrom heapq import *\nis_dev = 'vscode' in os.environ\nif is_dev:\n\tinF = open('in.txt', 'r')\n\toutF = open('out.txt', 'w')\n\ndef ins():\n\treturn list(map(int, input_().split(' ')))\n\ndef inss():\n\treturn list(input_().split(' '))\n\ndef inti():\n\treturn int(input_())\n\ndef input_():\n\tif is_dev:\n\t\treturn inF.readline()[:-1]\n\telse:\n\t\treturn input()\n\ndef ranin():\n\treturn range(int(input_()))\n\ndef print_(data):\n\tif is_dev:\n\t\toutF.write(str(data) + '\\n')\n\telse:\n\t\tprint(data)\n\ndef print_arr(data):\n\tprint_(' '.join(map(str, data)))\nepsilon = 1e-07\n\ndef q1():\n\tfor _ in ranin():\n\t\t(n, m, x) = ins()\n\t\tc = (x - 1) // n\n\t\tr = (x - 1) % n\n\t\tprint_(r * m + c + 1)\n\ndef q2():\n\tfor _ in ranin():\n\t\t(n, k) = ins()\n\t\ts = input_()\n\t\tprev = s.index('*')\n\t\tlast = s.rfind('*')\n\t\tlast_star = prev\n\t\tlast_star_solved = True\n\t\tc = 2 if last != prev else 1\n\t\tfor idx in range(prev + 1, last + 1):\n\t\t\tif idx - prev > k and (not last_star_solved):\n\t\t\t\tc += 1\n\t\t\t\tprev = last_star\n\t\t\t\tlast_star_solved = True\n\t\t\tif s[idx] == '*':\n\t\t\t\tlast_star = idx\n\t\t\t\tlast_star_solved = False\n\t\tprint_(c)\n\ndef q3():\n\ta = input_()\n\tb = input_()\n\tn = len(a)\n\tm = len(b)\n\tmaxi = 0\n\tfor si in range(n):\n\t\tsj = 0\n\t\tp1 = 0\n\t\tp2 = 1\n\t\twhile si < n and sj < m:\n\t\t\tif a[si] != b[sj]:\n\t\t\t\tp1 = p2\n\t\t\tmaxi = max(p2 - p1, maxi)\n\t\t\tp2 += 1\n\t\t\tsi += 1\n\t\t\tsj += 1\n\tfor sj in range(m):\n\t\tsi = 0\n\t\tp1 = 0\n\t\tp2 = 1\n\t\twhile si < n and sj < m:\n\t\t\tif a[si] != b[sj]:\n\t\t\t\tp1 = p2\n\t\t\tmaxi = max(p2 - p1, maxi)\n\t\t\tp2 += 1\n\t\t\tsi += 1\n\t\t\tsj += 1\n\treturn n - maxi + m - maxi\n\ndef q4():\n\tn = inti()\n\ta = ins()\n\ta = list(map(lambda x: -x, Counter(a).values()))\n\theapify(a)\n\twhile len(a) > 1:\n\t\ta1 = -heappop(a)\n\t\ta2 = -heappop(a)\n\t\tif a1 - 1:\n\t\t\theappush(a, -(a1 - 1))\n\t\tif a2 - 1:\n\t\t\theappush(a, -(a2 - 1))\n\treturn -a[0] if a else 0\n\ndef q5():\n\tn = inti()\n\ta = ins()\n\tp1 = [a[0]]\n\tp2 = [a[0]]\n\ts1 = {a[0]}\n\ts2 = {a[0]}\n\tsmallest_n = 1 if a[0] != 1 else 2\n\tk = 0\n\tfor idx in range(1, len(a)):\n\t\tif a[idx] != a[idx - 1]:\n\t\t\tp1.append(a[idx])\n\t\t\tp2.append(a[idx])\n\t\t\ts1.add(a[idx])\n\t\t\ts2.add(a[idx])\n\t\t\tk = idx\n\t\telse:\n\t\t\twhile a[idx] - (idx - k) in s2:\n\t\t\t\tk -= 1\n\t\t\tp2.append(a[idx] - (idx - k))\n\t\t\ts2.add(a[idx] - (idx - k))\n\t\t\twhile smallest_n in s1:\n\t\t\t\tsmallest_n += 1\n\t\t\tp1.append(smallest_n)\n\t\t\ts1.add(smallest_n)\n\treturn (p1, p2)\n\ndef q6():\n\tn = inti()\n\tr = ins()\n\tc = ins()\n\ta = list(zip(r, c))\n\ta.sort()\n\ts = 0\n\tcur_line = 0\n\tcl = 0\n\tpl = 1\n\tfor (i, j) in a:\n\t\tif not (i + j) % 2 == 1 and cl == i - j:\n\t\t\ts += i - pl\n\t\telse:\n\t\t\ts += abs(cur_line - (i - j) // 2)\n\t\tcur_line = (i - j) // 2\n\t\tcl = i - j\n\t\tpl = i\n\treturn s\nfor _ in ranin():\n\tp = q6()\n\tprint_(p)\nif is_dev:\n\toutF.close()\n\n\tdef compare_file():\n\t\tprint(open('out.txt', 'r').read() == open('outactual.txt', 'r').read())\n\tcompare_file()\n", "import sys\n\ndef get_ints():\n\treturn list(map(int, sys.stdin.readline().strip().split()))\n\ndef solve(N, R, C):\n\tans = 0\n\tsorted_idx = sorted(range(N), key=lambda i: (R[i], C[i]))\n\t(r, c) = (1, 1)\n\tfor i in sorted_idx:\n\t\tdiff = r - c\n\t\t(next_r, next_c) = (R[i], C[i])\n\t\tnext_diff = next_r - next_c\n\t\tif r == next_r and c == next_c:\n\t\t\tcontinue\n\t\tif diff == next_diff and (not r + c & 1):\n\t\t\tans += next_c - c\n\t\telif diff // 2 != next_diff // 2:\n\t\t\tans += abs(diff // 2 - next_diff // 2)\n\t\t(r, c) = (next_r, next_c)\n\treturn ans\nT = int(input())\nfor _ in range(T):\n\tN = int(input())\n\tR = get_ints()\n\tC = get_ints()\n\tans = solve(N, R, C)\n\tprint(ans)\n", "t = int(input())\nfor _ in range(t):\n\tn = int(input())\n\trc = []\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\tfor i in range(n):\n\t\trc.append([r[i], c[i]])\n\trc.sort()\n\tif rc[0] != [1, 1]:\n\t\trc.insert(0, [1, 1])\n\t\tn += 1\n\ts = 0\n\tfor i in range(n - 1):\n\t\tif rc[i][1] - rc[i][0] == rc[i + 1][1] - rc[i + 1][0] and (rc[i][1] + rc[i][0]) % 2 == 0:\n\t\t\ts += rc[i + 1][0] - rc[i][0]\n\t\telif rc[i][1] - rc[i][0] == rc[i + 1][1] - rc[i + 1][0] and (rc[i][1] + rc[i][0]) % 2 != 0:\n\t\t\ts += 0\n\t\telif (rc[i][1] + rc[i][0]) % 2 == 0:\n\t\t\ts += (rc[i + 1][0] - rc[i][0] - (rc[i + 1][1] - rc[i][1])) // 2\n\t\telse:\n\t\t\ts += (rc[i + 1][0] - rc[i][0] - (rc[i + 1][1] - rc[i][1]) + 1) // 2\n\tprint(s)\n", "for _ in range(int(input())):\n\tn = int(input())\n\tr = [int(x) for x in input().split()]\n\tc = [int(x) for x in input().split()]\n\t(sx, sy) = (1, 1)\n\tcost = 0\n\tfor (dx, dy) in sorted(zip(r, c)):\n\t\tsl = sx - sy\n\t\tdl = dx - dy\n\t\tif sl == dl:\n\t\t\tif sl % 2 == 0:\n\t\t\t\tpoints = dx - sx\n\t\t\telse:\n\t\t\t\tpoints = 0\n\t\telse:\n\t\t\tsdbl = sl // 2\n\t\t\tddbl = dl // 2\n\t\t\tif sdbl == ddbl:\n\t\t\t\tpoints = 0\n\t\t\telse:\n\t\t\t\tpoints = ddbl - sdbl\n\t\tcost += points\n\t\t(sx, sy) = (dx, dy)\n\tprint(f'{cost}')\n", "def f(x, y):\n\tif x == y:\n\t\treturn x - 1\n\telse:\n\t\treturn (x - y) // 2\n\ndef g(x, y):\n\treturn (x - y + 1) // 2\nfor _ in range(int(input())):\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\tl = []\n\tfor i in range(n):\n\t\tl.append([r[i], c[i]])\n\tl.sort()\n\tans = f(l[0][0], l[0][1])\n\tfor i in range(1, n):\n\t\tif (l[i - 1][0] + l[i - 1][1]) % 2 == 0:\n\t\t\tans += f(l[i][0] + 1 - l[i - 1][0], l[i][1] + 1 - l[i - 1][1])\n\t\telse:\n\t\t\tans += g(l[i][0] + 1 - l[i - 1][0], l[i][1] + 1 - l[i - 1][1])\n\tprint(ans)\n", "cases = int(input())\nfor cas in range(cases):\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\trc = []\n\tfor i in range(n):\n\t\trc.append((r[i], c[i]))\n\trc.sort(key=lambda x: x[0])\n\tif rc[0] != (1, 1):\n\t\trc.insert(0, (1, 1))\n\tans = 0\n\tfor i in range(0, len(rc) - 1):\n\t\t(sum1, sub1) = (rc[i][0] + rc[i][1], rc[i][0] - rc[i][1])\n\t\t(sum2, sub2) = (rc[i + 1][0] + rc[i + 1][1], rc[i + 1][0] - rc[i + 1][1])\n\t\tif sub1 == sub2:\n\t\t\tif sum1 % 2 == 0:\n\t\t\t\tans += (sum2 - sum1) // 2\n\t\t\telse:\n\t\t\t\tans += 0\n\t\telif sub1 % 2 == 0:\n\t\t\tans += (sub2 - sub1) // 2\n\t\telse:\n\t\t\tans += (sub2 - sub1 + 1) // 2\n\tprint(ans)\n", "def distance(current_point, next_point):\n\t(r1, c1) = (current_point[0], current_point[1])\n\t(r2, c2) = (next_point[0], next_point[1])\n\tif (r1 - c1) % 2 == 1:\n\t\tif (r2 - c2) % 2 == 1:\n\t\t\tif r1 - c1 == r2 - c2:\n\t\t\t\treturn 0\n\t\t\telse:\n\t\t\t\treturn (r2 - c2 - (r1 - c1)) // 2\n\t\telse:\n\t\t\treturn (r2 - c2 - (r1 - c1) + 1) // 2\n\telif (r2 - c2) % 2 == 1:\n\t\treturn (r2 - c2 - (r1 - c1) - 1) // 2\n\telif r1 - c1 == r2 - c2:\n\t\treturn r2 - r1\n\telse:\n\t\treturn (r2 - c2 - (r1 - c1)) // 2\n\ndef solve(n, lc, coordinates):\n\tcost = 0\n\tcurrent_point = (1, 1)\n\tcoordinates_index = 0\n\twhile coordinates_index < lc:\n\t\tnext_point = coordinates[coordinates_index]\n\t\tcost = cost + distance(current_point, next_point)\n\t\tcurrent_point = next_point\n\t\tcoordinates_index += 1\n\treturn cost\nt = int(input())\nfor tc in range(t):\n\tn = int(input())\n\trs = [int(r) for r in input().split()]\n\tcs = [int(c) for c in input().split()]\n\tcoordinates = []\n\tfor i in range(n):\n\t\tcoordinates.append((rs[i], cs[i]))\n\tcoordinates = sorted(coordinates)\n\tlc = len(coordinates)\n\tprint(solve(n, lc, coordinates))\n", "def minCost(a, b):\n\tif (b[0] + b[1]) % 2 == 0 and b[0] - b[1] == a[0] - a[1]:\n\t\treturn b[0] - a[0]\n\tdiagA = (a[0] - a[1]) // 2\n\tdiagB = (b[0] - b[1]) // 2\n\treturn diagB - diagA\nt = int(input())\nfor i in range(t):\n\tn = int(input())\n\tnodes = list(zip(map(int, input().split()), map(int, input().split())))\n\tnodes.insert(0, (1, 1))\n\tnodes.sort()\n\tres = 0\n\tfor i in range(len(nodes) - 1):\n\t\tres += minCost(nodes[i], nodes[i + 1])\n\tprint(res)\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 bisect import *\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 AI():\n\treturn map(int, open(0).read().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 = 10\n\tn = random.randint(1, N)\n\ta = RLI(n, 0, n - 1)\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 = float('inf')\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)]\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 divisor(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 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\nshow_flg = False\nshow_flg = True\nans = 0\nfor _ in range(I()):\n\tans = 0\n\tn = I() + 1\n\tr = [1] + LI()\n\tc = [1] + LI()\n\tp = [(i - j, (i, j)) for (i, j) in zip(r, c)]\n\tp.sort()\n\tfor i in range(n - 1):\n\t\t(k1, (r1, c1)) = p[i]\n\t\t(k2, (r2, c2)) = p[i + 1]\n\t\tif k1 == k2 and k1 % 2 == 0:\n\t\t\tans += c2 - c1\n\t\telif k1 == k2 and k1 % 2 == 1:\n\t\t\tans += 0\n\t\telif k1 % 2 == 0:\n\t\t\tans += (k2 - k1) // 2\n\t\telse:\n\t\t\tans += (k2 - k1 + 1) // 2\n\tprint(ans)\n", "def solve():\n\tn = int(input())\n\tpoints = []\n\tx = input()\n\tx = [int(i) for i in x.split(' ')]\n\tfor i in x:\n\t\tpoints.append([i, 0])\n\ty = input()\n\ty = [int(i) for i in y.split(' ')]\n\tfor (i, v) in enumerate(y):\n\t\tpoints[i][1] = v\n\tpoints.sort()\n\tans = 0\n\tstart = [1, 1]\n\tfor (x, y) in points:\n\t\t(a, b) = start\n\t\tif x - y == a - b:\n\t\t\tif (a - b) % 2 == 0:\n\t\t\t\tans += y - b\n\t\telse:\n\t\t\tans += (x - y) // 2 - (a - b) // 2\n\t\tstart = [x, y]\n\tprint(ans)\n\ndef main():\n\tt = int(input())\n\twhile t:\n\t\tsolve()\n\t\tt -= 1\nmain()\n", "import queue\nimport math\nimport sys\nfrom collections import deque\n\ndef path_exists(node1, node2):\n\t(r1, c1) = node1\n\t(r2, c2) = node2\n\treturn r1 in range(1, r2 + 1) and c2 in range(c1, c1 + r2 - r1 + 1)\n\ndef min_cost(node1, node2):\n\t(r1, c1) = node1\n\t(r2, c2) = node2\n\tans = 0\n\tif c2 == c1:\n\t\tans = (r2 - r1) // 2\n\t\tif (r1 + c1) % 2 == 1 and (r2 - r1) % 2 == 1:\n\t\t\tans += 1\n\telif r2 - r1 == c2 - c1:\n\t\tans = (r2 - r1) * int((r1 + c1) % 2 == 0)\n\telse:\n\t\t(r1, c1) = node1\n\t\tif (r1 + c1) % 2 == 0:\n\t\t\tr1 += 1\n\t\tr1 = r1 + (c2 - c1)\n\t\tc1 = c2\n\t\tans = (r2 - r1) // 2 + int((r2 - r1) % 2 == 1)\n\treturn ans\nt = int(input())\nfor _ in range(t):\n\tn = int(input())\n\tR = list(map(int, input().split(' ')))\n\tC = list(map(int, input().split(' ')))\n\tnodes = [(R[i], C[i]) for i in range(n)]\n\tnodes.sort(key=lambda p: p[0])\n\tminimum_cost = min_cost((1, 1), nodes[0])\n\tfor j in range(n - 1):\n\t\tminimum_cost += min_cost(nodes[j], nodes[j + 1])\n\tprint(minimum_cost)\n", "from sys import stdin, stdout\n\ndef triangular_paths(n, r_a, c_a):\n\trc_a = [[1, 1]]\n\tfor i in range(n):\n\t\trc_a.append([r_a[i], c_a[i]])\n\trc_a.sort(key=lambda x: x[0])\n\tres = 0\n\tfor i in range(1, n + 1):\n\t\tr1 = rc_a[i - 1][0]\n\t\tc1 = rc_a[i - 1][1]\n\t\tr2 = rc_a[i][0]\n\t\tc2 = rc_a[i][1]\n\t\tif (r1 + c1) % 2 == 1 and (r2 + c2) % 2 == 1:\n\t\t\tres += cal_1(r1, c1, r2, c2)\n\t\telif (r1 + c1) % 2 == 1 and (r2 + c2) % 2 == 0:\n\t\t\tres += cal_2(r1, c1, r2, c2)\n\t\telif (r1 + c1) % 2 == 0 and (r2 + c2) % 2 == 1:\n\t\t\tres += cal_3(r1, c1, r2, c2)\n\t\telif (r1 + c1) % 2 == 0 and (r2 + c2) % 2 == 0:\n\t\t\tres += cal_4(r1, c1, r2, c2)\n\treturn res\n\ndef cal_1(r1, c1, r2, c2):\n\treturn (r2 - (c2 - c1) - r1) // 2\n\ndef cal_2(r1, c1, r2, c2):\n\treturn cal_1(r1, c1, r2 - 1, c2) + 1\n\ndef cal_3(r1, c1, r2, c2):\n\treturn cal_1(r1 + 1, c1, r2, c2)\n\ndef cal_4(r1, c1, r2, c2):\n\tif r1 - c1 == r2 - c2:\n\t\treturn c2 - c1\n\telse:\n\t\treturn cal_2(r1 + 1, c1, r2, c2)\nt = int(stdin.readline())\nfor _ in range(t):\n\tn = int(stdin.readline())\n\tr_a = list(map(int, stdin.readline().split()))\n\tc_a = list(map(int, stdin.readline().split()))\n\tr = triangular_paths(n, r_a, c_a)\n\tstdout.write(str(r) + '\\n')\n", "import sys\nsys.setrecursionlimit(10 ** 5)\nint1 = lambda x: int(x) - 1\np2D = lambda x: print(*x, sep='\\n')\n\ndef II():\n\treturn int(sys.stdin.buffer.readline())\n\ndef LI():\n\treturn list(map(int, sys.stdin.buffer.readline().split()))\n\ndef LI1():\n\treturn list(map(int1, sys.stdin.buffer.readline().split()))\n\ndef LLI(rows_number):\n\treturn [LI() for _ in range(rows_number)]\n\ndef LLI1(rows_number):\n\treturn [LI1() 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()\ndij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]\ninf = 10 ** 16\nmd = 10 ** 9 + 7\nfor _ in range(II()):\n\tn = II()\n\trr = LI()\n\tcc = LI()\n\trc = [(r, c) for (r, c) in zip(rr, cc)]\n\trc.sort()\n\tans = 0\n\tnow = 0\n\tpr = 1\n\tfor (r, c) in rc:\n\t\tnxt = r - c\n\t\tif now < nxt:\n\t\t\tif now & 1:\n\t\t\t\tans += (nxt - now + 1) // 2\n\t\t\telse:\n\t\t\t\tans += (nxt - now) // 2\n\t\telif now > nxt:\n\t\t\tif now & 1:\n\t\t\t\tans += (nxt - now) // 2\n\t\t\telse:\n\t\t\t\tans += (nxt - now + 1) // 2\n\t\telif now & 1 == 0:\n\t\t\tans += r - pr\n\t\tnow = nxt\n\t\tpr = r\n\tprint(ans)\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\n\ndef main():\n\tfor _ in range(int(input())):\n\t\tinput()\n\t\ta = sorted(zip(map(int, input().split()), map(int, input().split())))\n\t\tans = 0\n\t\t(x, y) = (1, 1)\n\t\tfor (u, v) in a:\n\t\t\t(xx, yy) = (u, v)\n\t\t\tif u - v == x - y:\n\t\t\t\tif (u + v) % 2 == 0:\n\t\t\t\t\tans += u - x\n\t\t\telse:\n\t\t\t\tu -= x - 1\n\t\t\t\tv -= y - 1\n\t\t\t\tans += (u - v + (x + y) % 2) // 2\n\t\t\t(x, y) = (xx, yy)\n\t\tprint(ans)\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", "for z in range(int(input())):\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\ta = []\n\tb = 0\n\ta1 = 0\n\tfor i in range(n):\n\t\tb = max(b, r[i] - c[i])\n\t\tif (r[i] - c[i]) % 2 == 0:\n\t\t\ta.append([r[i] - c[i], r[i]])\n\t\t\ta1 += 1\n\tb //= 2\n\tc = 0\n\tif a1 != 0:\n\t\ta.sort()\n\t\tfor i in range(1, len(a)):\n\t\t\tif a[i][0] != a[i - 1][0]:\n\t\t\t\tif a[i - 1][0] == 0 and r[0] != 1:\n\t\t\t\t\tb += a[c][1] - 1\n\t\t\t\tb += a[i - 1][1] - a[c][1]\n\t\t\t\tc = i\n\t\tb += a[-1][1] - a[c][1]\n\t\tif a[-1][0] == 0 and r[0] != 1:\n\t\t\tb += a[c][1] - 1\n\tprint(b)\n", "import sys, math, itertools\nfrom collections import Counter, deque, defaultdict\nfrom bisect import bisect_left, bisect_right\nfrom heapq import heappop, heappush, heapify\nfrom copy import deepcopy, copy\nmod = 10 ** 9 + 7\nINF = float('inf')\n\ndef inp():\n\treturn int(sys.stdin.readline())\n\ndef inpl():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef inpl_1():\n\treturn list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))\n\ndef inps():\n\treturn sys.stdin.readline()\n\ndef inpsl(x):\n\ttmp = sys.stdin.readline()\n\treturn list(tmp[:x])\n\ndef err(x):\n\tprint(x)\n\texit()\nfor _ in range(inp()):\n\tn = inp()\n\tr = inpl()\n\tc = inpl()\n\trc = [(r[i], c[i]) for i in range(n)]\n\trc.sort()\n\t(_sa, _r) = (0, 1)\n\tres = 0\n\tfor (r, c) in rc:\n\t\tsa = r - c\n\t\tif _sa % 2 == 0:\n\t\t\tif _sa == sa:\n\t\t\t\tres += r - _r\n\t\t\telse:\n\t\t\t\tres += (sa - _sa) // 2\n\t\telse:\n\t\t\ttmp = sa - _sa\n\t\t\tres += -(-tmp // 2)\n\t\t(_sa, _r) = (sa, r)\n\tprint(res)\n", "for nt in range(int(input())):\n\tn = int(input())\n\tb = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\ta = [[b[i], c[i]] for i in range(n)]\n\ta.sort()\n\tif a[0] == [1, 1]:\n\t\ta.pop(0)\n\t\tn -= 1\n\tans = 0\n\ti = 0\n\tcurr = [1, 1]\n\twhile i < n and a[i][0] == a[i][1]:\n\t\tans += a[i][0] - curr[0]\n\t\tcurr = a[i]\n\t\ti += 1\n\todd = sum(curr) % 2\n\twhile i < n:\n\t\tif a[i][0] - a[i][1] == curr[0] - curr[1]:\n\t\t\tif not odd:\n\t\t\t\tans += a[i][0] - curr[0]\n\t\telif odd:\n\t\t\tans += (a[i][0] - a[i][1] - (curr[0] - curr[1]) - 1) // 2 + 1\n\t\telse:\n\t\t\tans += (a[i][0] - a[i][1] - (curr[0] - curr[1])) // 2\n\t\tcurr = a[i]\n\t\todd = sum(curr) % 2\n\t\ti += 1\n\tprint(ans)\n", "import collections\nimport heapq\n\ndef isLeftArrow(r, c):\n\treturn (r + c) % 2 == 0\n\ndef isRightArrow(r, c):\n\treturn (r + c) % 2 == 1\n\ndef calcDist(r1, c1, r2, c2):\n\tif r1 - c1 == r2 - c2:\n\t\treturn 0 if isRightArrow(r1, c1) else r2 - r1\n\tr2 -= r1 - 1\n\tc2 -= c1 - 1\n\tif isLeftArrow(r1, c1):\n\t\treturn (r2 - c2) // 2\n\telse:\n\t\treturn (r2 - c2 + 1) // 2\n\ndef process(n, r, c):\n\tpts = []\n\tfor i in range(n):\n\t\tpts.append((r[i], c[i]))\n\tpts.sort()\n\t(curR, curC) = (1, 1)\n\tres = 0\n\tfor (nextR, nextC) in pts:\n\t\tres += calcDist(curR, curC, nextR, nextC)\n\t\tcurR = nextR\n\t\tcurC = nextC\n\tprint(res)\ntcs = int(input())\nfor tc in range(tcs):\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\tprocess(n, r, c)\n", "from collections import defaultdict\nfrom collections import deque\nfor _ in range(int(input())):\n\tn = int(input())\n\tr = [int(i) for i in input().split()]\n\tc = [int(i) for i in input().split()]\n\ta = [(0, 1, 1)]\n\tfor i in range(n):\n\t\ta.append((r[i] - c[i], r[i], c[i]))\n\ta.sort()\n\tans = 0\n\tfor i in range(1, n + 1):\n\t\t(prev_d_i, prev_r_i, prev_c_i) = a[i - 1]\n\t\t(d_i, r_i, c_i) = a[i]\n\t\tif prev_d_i == d_i:\n\t\t\tif d_i % 2 == 0:\n\t\t\t\tans += r_i - prev_r_i\n\t\telif prev_d_i % 2 == 1:\n\t\t\tans += (d_i - prev_d_i + 1) // 2\n\t\telse:\n\t\t\tans += (d_i - prev_d_i) // 2\n\tprint(ans)\n", "import sys\nimport math\nfrom collections import defaultdict, Counter, deque\nimport 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')\nt = int(input())\nfor i in range(t):\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\tl = [[1, 1]]\n\tfor j in range(n):\n\t\tl.append([r[j], c[j]])\n\tl.sort()\n\tans = 0\n\tfor j in range(1, n + 1):\n\t\tif l[j][1] == l[j - 1][1]:\n\t\t\tif (l[j - 1][0] + l[j - 1][1]) % 2 == 0:\n\t\t\t\tans += (l[j][0] - l[j - 1][0]) // 2\n\t\t\telse:\n\t\t\t\tans += (l[j][0] - l[j - 1][0] + 1) // 2\n\t\telif l[j][0] - l[j][1] == l[j - 1][0] - l[j - 1][1]:\n\t\t\tif (l[j - 1][0] + l[j - 1][1]) % 2 == 0:\n\t\t\t\tans += l[j][0] - l[j - 1][0]\n\t\telse:\n\t\t\td = l[j - 1][0] - l[j - 1][1]\n\t\t\tif (l[j - 1][0] + l[j - 1][1]) % 2 == 0:\n\t\t\t\td += 1\n\t\t\tnew = [l[j][1] + d, l[j][1]]\n\t\t\tif (new[0] + new[1]) % 2 == 0:\n\t\t\t\tans += (l[j][0] - new[0]) // 2\n\t\t\telse:\n\t\t\t\tans += (l[j][0] - new[0] + 1) // 2\n\tprint(ans)\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nimport threading\nfrom bisect import bisect_right\nfrom math import gcd, log\nfrom collections import Counter, defaultdict\nfrom pprint import pprint\nfrom itertools import permutations\nfrom bisect import bisect_left\nimport heapq\n\ndef main():\n\tn = int(input())\n\tarr = list(map(int, input().split()))\n\tbrr = list(map(int, input().split()))\n\ta = 1\n\td1 = defaultdict(list)\n\td1[0].append(1)\n\tfor i in range(n):\n\t\ta = min(a, brr[i] - arr[i])\n\t\tif (arr[i] - brr[i]) % 2 == 0:\n\t\t\td1[arr[i] - brr[i]].append(brr[i])\n\tans = 0\n\tfor li in d1.values():\n\t\tans += max(li) - min(li)\n\tprint(ans + abs(a) // 2)\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 _ in range(int(input())):\n\tmain()\n", "import io, os, sys\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\nimport heapq\nT = int(input())\nr = 1\nwhile r <= T:\n\tn = int(input())\n\tarr_r = list(map(int, input().split()))\n\tarr_c = list(map(int, input().split()))\n\tseq = [[1, 1]]\n\tfor i in range(n):\n\t\tseq.append([arr_r[i], arr_c[i]])\n\tseq = sorted(seq)\n\tans = 0\n\tfor i in range(1, n + 1):\n\t\tdiff = seq[i][0] - seq[i - 1][0] - (seq[i][1] - seq[i - 1][1])\n\t\tif diff == 0 and (seq[i - 1][0] + seq[i - 1][1]) % 2 == 0:\n\t\t\tans += seq[i][0] - seq[i - 1][0]\n\t\telif (seq[i - 1][0] + seq[i - 1][1]) % 2 == 0:\n\t\t\tans += diff // 2\n\t\telif (seq[i - 1][0] + seq[i - 1][1]) % 2 == 1:\n\t\t\tans += (diff + 1) // 2\n\tprint(ans)\n\tr += 1\n", "for case in range(int(input())):\n\tn = int(input())\n\tX = list(map(int, input().split()))\n\tY = list(map(int, input().split()))\n\tli = []\n\tfor i in range(n):\n\t\tx = X[i]\n\t\ty = Y[i]\n\t\tli.append((abs(x - y + 1), min(x, y)))\n\tli.sort()\n\tprvblk = 1\n\tprvplc = 1\n\tcost = 0\n\tfor (blk, plc) in li:\n\t\thor = blk - prvblk\n\t\tver = plc - prvplc\n\t\tif hor == 0:\n\t\t\tif prvblk % 2:\n\t\t\t\tcost += ver\n\t\telif prvblk % 2:\n\t\t\tcost += hor // 2\n\t\telse:\n\t\t\tcost += (hor + 1) // 2\n\t\tprvblk = blk\n\t\tprvplc = plc\n\tprint(cost)\n", "import copy\n\ndef helper(a, b):\n\tif a == b:\n\t\treturn 0\n\t(x0, y0) = a\n\t(x1, y1) = b\n\tif (x0 + y0) % 2 == 0:\n\t\tx0 += 1\n\ty0 += x1 - x0\n\tif y1 > y0:\n\t\treturn x1 - x0 + 1\n\telif y1 == y0:\n\t\treturn 0\n\telse:\n\t\treturn (y0 - y1 + 1) // 2\nt = int(input())\nfor i in range(t):\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\tpool = [[1, 1]]\n\tfor i in range(n):\n\t\tpool.append([r[i], c[i]])\n\tpool.sort()\n\tres = 0\n\tfor i in range(1, n + 1):\n\t\tres += helper(pool[i - 1], pool[i])\n\tprint(res)\n", "import sys\ninput = sys.stdin.readline\n\ndef cost(a, b):\n\trdiff = b[0] - a[0]\n\tcdiff = b[1] - a[1]\n\tif (a[0] + a[1]) % 2 == 0:\n\t\tif rdiff == cdiff:\n\t\t\treturn rdiff\n\t\tif rdiff == cdiff + 1:\n\t\t\treturn 0\n\t\tif rdiff % 2 == 0:\n\t\t\treturn rdiff // 2 - (cdiff + 1) // 2\n\t\tif rdiff % 2 == 1:\n\t\t\treturn rdiff // 2 - cdiff // 2\n\tif (a[0] + a[1]) % 2 == 1:\n\t\tif rdiff == cdiff:\n\t\t\treturn 0\n\t\tif rdiff == cdiff + 1 or rdiff == cdiff + 2:\n\t\t\treturn 1\n\t\tif rdiff % 2 == 0:\n\t\t\treturn (rdiff + 1) // 2 - cdiff // 2\n\t\tif rdiff % 2 == 1:\n\t\t\treturn (rdiff + 1) // 2 - (cdiff + 1) // 2\nt = int(input())\nfor i in range(t):\n\tn = int(input())\n\tr = [int(x) for x in input().split()]\n\tc = [int(x) for x in input().split()]\n\tpoints = sorted(zip(r, c))\n\tans = cost((1, 1), points[0])\n\tfor i in range(n - 1):\n\t\tans += cost(points[i], points[i + 1])\n\tprint(ans)\n", "import sys\nP = lambda : map(int, sys.stdin.readline().split())\nfor _ in range(*P()):\n\t(n,) = P()\n\td = [(1, 1)] + sorted(zip(P(), P()))\n\ta = 0\n\tfor i in range(n):\n\t\t(r, c) = d[i]\n\t\tv = r - c\n\t\t(R, C) = d[i + 1]\n\t\ta += (R - C) // 2 - v // 2 + (R - r) * (v & 1 < 1 and v == R - C)\n\tprint(a)\n", "from bisect import *\nfrom collections import *\nfrom math import gcd, ceil, sqrt, floor, inf\nfrom heapq import *\nfrom itertools import *\nfrom operator import add, mul, sub, xor, truediv, floordiv\nfrom functools import *\nimport 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')\n\ndef RL():\n\treturn map(int, sys.stdin.readline().rstrip().split())\n\ndef RLL():\n\treturn list(map(int, sys.stdin.readline().rstrip().split()))\n\ndef N():\n\treturn int(input())\n\ndef A(n):\n\treturn [0] * n\n\ndef AI(n, x):\n\treturn [x] * n\n\ndef A2(n, m):\n\treturn [[0] * m for i in range(n)]\n\ndef G(n):\n\treturn [[] for i in range(n)]\n\ndef GP(it):\n\treturn [[ch, len(list(g))] for (ch, g) in groupby(it)]\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\nmod = 10 ** 9 + 7\nfarr = [1]\nifa = []\n\ndef fact(x, mod=0):\n\tif mod:\n\t\twhile x >= len(farr):\n\t\t\tfarr.append(farr[-1] * len(farr) % mod)\n\telse:\n\t\twhile x >= len(farr):\n\t\t\tfarr.append(farr[-1] * len(farr))\n\treturn farr[x]\n\ndef ifact(x, mod):\n\tglobal ifa\n\tfact(x, mod)\n\tifa.append(pow(farr[-1], mod - 2, mod))\n\tfor i in range(x, 0, -1):\n\t\tifa.append(ifa[-1] * i % mod)\n\tifa.reverse()\n\ndef per(i, j, mod=0):\n\tif i < j:\n\t\treturn 0\n\tif not mod:\n\t\treturn fact(i) // fact(i - j)\n\treturn farr[i] * ifa[i - j] % mod\n\ndef com(i, j, mod=0):\n\tif i < j:\n\t\treturn 0\n\tif not mod:\n\t\treturn per(i, j) // fact(j)\n\treturn per(i, j, mod) * ifa[j] % mod\n\ndef catalan(n):\n\treturn com(2 * n, n) // (n + 1)\n\ndef isprime(n):\n\tfor i in range(2, int(n ** 0.5) + 1):\n\t\tif n % i == 0:\n\t\t\treturn False\n\treturn True\n\ndef floorsum(a, b, c, n):\n\tif a == 0:\n\t\treturn b // c * (n + 1)\n\tif a >= c or b >= c:\n\t\treturn floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2\n\tm = (a * n + b) // c\n\treturn n * m - floorsum(c, c - b - 1, a, m - 1)\n\ndef inverse(a, m):\n\ta %= m\n\tif a <= 1:\n\t\treturn a\n\treturn (1 - inverse(m, a) * m) // a % m\n\ndef lowbit(n):\n\treturn n & -n\n\nclass BIT:\n\n\tdef __init__(self, arr):\n\t\tself.arr = arr\n\t\tself.n = len(arr) - 1\n\n\tdef update(self, x, v):\n\t\twhile x <= self.n:\n\t\t\tself.arr[x] += v\n\t\t\tx += x & -x\n\n\tdef query(self, x):\n\t\tans = 0\n\t\twhile x:\n\t\t\tans += self.arr[x]\n\t\t\tx &= x - 1\n\t\treturn ans\n\nclass ST:\n\n\tdef __init__(self, arr):\n\t\tn = len(arr)\n\t\tmx = n.bit_length()\n\t\tself.st = [[0] * mx for i in range(n)]\n\t\tfor i in range(n):\n\t\t\tself.st[i][0] = arr[i]\n\t\tfor j in range(1, mx):\n\t\t\tfor i in range(n - (1 << j) + 1):\n\t\t\t\tself.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])\n\n\tdef query(self, l, r):\n\t\tif l > r:\n\t\t\treturn -inf\n\t\ts = (r + 1 - l).bit_length() - 1\n\t\treturn max(self.st[l][s], self.st[r - (1 << s) + 1][s])\n\nclass UFS:\n\n\tdef __init__(self, n):\n\t\tself.parent = [i for i in range(n)]\n\t\tself.ranks = [0] * n\n\n\tdef find(self, x):\n\t\tif x != self.parent[x]:\n\t\t\tself.parent[x] = self.find(self.parent[x])\n\t\treturn self.parent[x]\n\n\tdef union(self, u, v):\n\t\t(pu, pv) = (self.find(u), self.find(v))\n\t\tif pu == pv:\n\t\t\treturn False\n\t\tif self.ranks[pu] >= self.ranks[pv]:\n\t\t\tself.parent[pv] = pu\n\t\t\tif self.ranks[pv] == self.ranks[pu]:\n\t\t\t\tself.ranks[pu] += 1\n\t\telse:\n\t\t\tself.parent[pu] = pv\n\ndef Prime(n):\n\tc = 0\n\tprime = []\n\tflag = [0] * (n + 1)\n\tfor i in range(2, n + 1):\n\t\tif not flag[i]:\n\t\t\tprime.append(i)\n\t\t\tc += 1\n\t\tfor j in range(c):\n\t\t\tif i * prime[j] > n:\n\t\t\t\tbreak\n\t\t\tflag[i * prime[j]] = prime[j]\n\t\t\tif i % prime[j] == 0:\n\t\t\t\tbreak\n\treturn prime\n\ndef dij(s, graph):\n\td = {}\n\td[s] = 0\n\theap = [(0, s)]\n\tseen = set()\n\twhile heap:\n\t\t(dis, u) = heappop(heap)\n\t\tif u in seen:\n\t\t\tcontinue\n\t\tseen.add(u)\n\t\tfor (v, w) in graph[u]:\n\t\t\tif v not in d or d[v] > d[u] + w:\n\t\t\t\td[v] = d[u] + w\n\t\t\t\theappush(heap, (d[v], v))\n\treturn d\n\ndef bell(s, g):\n\tdis = AI(n, inf)\n\tdis[s] = 0\n\tfor i in range(n - 1):\n\t\tfor (u, v, w) in edge:\n\t\t\tif dis[v] > dis[u] + w:\n\t\t\t\tdis[v] = dis[u] + w\n\tchange = A(n)\n\tfor i in range(n):\n\t\tfor (u, v, w) in edge:\n\t\t\tif dis[v] > dis[u] + w:\n\t\t\t\tdis[v] = dis[u] + w\n\t\t\t\tchange[v] = 1\n\treturn dis\n\ndef lcm(a, b):\n\treturn a * b // gcd(a, b)\n\ndef lis(nums):\n\tres = []\n\tfor k in nums:\n\t\ti = bisect.bisect_left(res, k)\n\t\tif i == len(res):\n\t\t\tres.append(k)\n\t\telse:\n\t\t\tres[i] = k\n\treturn len(res)\n\ndef RP(nums):\n\tn = len(nums)\n\ts = set(nums)\n\td = {}\n\tfor (i, k) in enumerate(sorted(s), 1):\n\t\td[k] = i\n\tbi = BIT([0] * (len(s) + 1))\n\tans = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tans += bi.query(d[nums[i]] - 1)\n\t\tbi.update(d[nums[i]], 1)\n\treturn ans\n\nclass DLN:\n\n\tdef __init__(self, val):\n\t\tself.val = val\n\t\tself.pre = None\n\t\tself.next = None\n\ndef nb(i, j, n, m):\n\tfor (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:\n\t\tif 0 <= ni < n and 0 <= nj < m:\n\t\t\tyield (ni, nj)\n\ndef topo(n):\n\tq = deque()\n\tres = []\n\tfor i in range(1, n + 1):\n\t\tif ind[i] == 0:\n\t\t\tq.append(i)\n\t\t\tres.append(i)\n\twhile q:\n\t\tu = q.popleft()\n\t\tfor v in g[u]:\n\t\t\tind[v] -= 1\n\t\t\tif ind[v] == 0:\n\t\t\t\tq.append(v)\n\t\t\t\tres.append(v)\n\treturn res\n\n@bootstrap\ndef gdfs(r, p):\n\tfor ch in g[r]:\n\t\tif ch != p:\n\t\t\tyield gdfs(ch, r)\n\tyield None\n\ndef f(i, j):\n\t(a, b) = res[i]\n\t(c, d) = res[j]\n\tfi = a - b\n\tse = c - d\n\tif fi == se:\n\t\tif fi & 1:\n\t\t\treturn 0\n\t\telse:\n\t\t\treturn d - b\n\telse:\n\t\treturn (se - fi) // 2 + (fi & (1 & se - fi))\nt = N()\nfor i in range(t):\n\tn = N()\n\tr = RLL()\n\tc = RLL()\n\tres = [(1, 1)] + sorted([(x, y) for (x, y) in zip(r, c)])\n\tans = 0\n\tfor i in range(1, n + 1):\n\t\tans += f(i - 1, i)\n\tprint(ans)\n", "import sys\nfrom collections import Counter\ninput = sys.stdin.readline\nt = int(input())\nfor _ in range(t):\n\tn = int(input())\n\tans = 0\n\tMUL = 1000000007\n\tr = list(map(int, input().split()))\n\tr.append(1)\n\tc = list(map(int, input().split()))\n\tc.append(1)\n\ta = [r[i] * MUL + c[i] for i in range(n + 1)]\n\ta.sort()\n\tfor i in range(1, n + 1):\n\t\tfrom_r = a[i - 1] // MUL\n\t\tfrom_c = a[i - 1] % MUL\n\t\tto_r = a[i] // MUL\n\t\tto_c = a[i] % MUL\n\t\tend_c = 0\n\t\tif (from_r + from_c) % 2 == 0:\n\t\t\tend_c = from_c + (to_r - from_r - 1)\n\t\telse:\n\t\t\tend_c = from_c + (to_r - from_r)\n\t\tif end_c == to_c:\n\t\t\tcontinue\n\t\tif end_c < to_c:\n\t\t\tans += to_r - from_r\n\t\t\tcontinue\n\t\tdif = end_c - to_c\n\t\tans += dif // 2\n\t\tif dif % 2 == 1:\n\t\t\tans += 1\n\tprint(ans)\n", "for t in range(int(input())):\n\tn = int(input())\n\tr_arr = tuple(map(int, input().split()))\n\tc_arr = tuple(map(int, input().split()))\n\tr_rminusc = [(r, r - c, c) for (r, c) in zip(r_arr, c_arr)]\n\tr_rminusc.sort()\n\tcost = 0\n\tcurrent_pos = (1, 0, 1)\n\tfor tup3 in r_rminusc:\n\t\tdiff1 = current_pos[1]\n\t\tdiff2 = tup3[1]\n\t\t(c11, c12) = divmod(diff1, 2)\n\t\t(c21, c22) = divmod(diff2, 2)\n\t\tif c11 != c21:\n\t\t\tcost += c21 - c11\n\t\telif c22 == 0 and c12 == 0:\n\t\t\tcost += tup3[0] - current_pos[0]\n\t\tcurrent_pos = tup3\n\tprint(cost)\n", "import sys\ninput = sys.stdin.readline\n\ndef calc1(r1, r2, c1, c2):\n\tif (r1 + c1) % 2 == 1:\n\t\treturn 0\n\treturn r2 - r1\n\ndef calc2(r1, r2, c1, c2):\n\tdiff = r2 - c2 - (r1 - c1)\n\tif (r1 + c1) % 2 == 0:\n\t\treturn diff // 2\n\treturn (diff + 1) // 2\nt = int(input())\nfor _ in range(t):\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\tpoints = [(1, 1)] + sorted(zip(r, c), key=lambda x: x[0])\n\tans = 0\n\tfor i in range(1, n + 1):\n\t\tr1 = points[i - 1][0]\n\t\tr2 = points[i][0]\n\t\tc1 = points[i - 1][1]\n\t\tc2 = points[i][1]\n\t\tif r2 - c2 - (r1 - c1):\n\t\t\tans += calc2(r1, r2, c1, c2)\n\t\telse:\n\t\t\tans += calc1(r1, r2, c1, c2)\n\tprint(ans)\n", "def num_path2(list_pairs):\n\tcnt = 0\n\t(l, r) = (1, 1)\n\tind = 0\n\twhile True:\n\t\tif ind == len(list_pairs):\n\t\t\tbreak\n\t\t(l_targ, r_targ) = list_pairs[ind]\n\t\tif (l, r) == (l_targ, r_targ):\n\t\t\tind += 1\n\t\telif r_targ == r:\n\t\t\tcum = (l_targ - l) // 2\n\t\t\tif (l_targ - l) % 2 == 1:\n\t\t\t\tif (r + l) % 2 == 1:\n\t\t\t\t\tcum += 1\n\t\t\tcnt += cum\n\t\t\t(l, r) = (l_targ, r_targ)\n\t\t\tind += 1\n\t\telif l_targ - l == r_targ - r:\n\t\t\tif (r + l) % 2 == 0:\n\t\t\t\tcnt += l_targ - l\n\t\t\t(l, r) = (l_targ, r_targ)\n\t\t\tind += 1\n\t\telse:\n\t\t\tr_cand = r if (l + r) % 2 == 0 else r + 1\n\t\t\tif 0 <= r_targ - r_cand <= l_targ - l - 1:\n\t\t\t\tr = r_cand\n\t\t\telse:\n\t\t\t\tcnt += 1\n\t\t\t\tr = r + 1 if (l + r) % 2 == 0 else r\n\t\t\tl += 1\n\t\tprint(l, r, cnt)\n\treturn cnt\n\ndef num_path(list_pairs):\n\tcnt = 0\n\t(l, r) = (1, 1)\n\tind = 0\n\twhile True:\n\t\tif ind == len(list_pairs):\n\t\t\tbreak\n\t\t(l_targ, r_targ) = list_pairs[ind]\n\t\tif (l, r) == (l_targ, r_targ):\n\t\t\tind += 1\n\t\telif r_targ == r:\n\t\t\tcum = (l_targ - l) // 2\n\t\t\tif (l_targ - l) % 2 == 1:\n\t\t\t\tif (r + l) % 2 == 1:\n\t\t\t\t\tcum += 1\n\t\t\tcnt += cum\n\t\t\t(l, r) = (l_targ, r_targ)\n\t\t\tind += 1\n\t\telif l_targ - l == r_targ - r:\n\t\t\tif (r + l) % 2 == 0:\n\t\t\t\tcnt += l_targ - l\n\t\t\t(l, r) = (l_targ, r_targ)\n\t\t\tind += 1\n\t\telif (r + l) % 2 == 1:\n\t\t\tjump = r_targ - r\n\t\t\t(l, r) = (l + jump, r + jump)\n\t\telse:\n\t\t\t(l, r) = (l + 1, r)\n\treturn cnt\nnum = int(input())\nfor i in range(num):\n\tinput()\n\tlist_r = [int(el) for el in input().split()]\n\tlist_c = [int(el) for el in input().split()]\n\tlist_pairs = [(r, c) for (r, c) in zip(list_r, list_c)]\n\tlist_pairs.sort()\n\tprint(num_path(list_pairs))\n", "from sys import stdin, stdout\nimport heapq\nfrom collections import defaultdict\nimport math\nimport bisect\n\ndef main():\n\tt = int(stdin.readline())\n\tfor _ in range(t):\n\t\tn = int(stdin.readline())\n\t\tarr = list(map(int, stdin.readline().split()))\n\t\tarr2 = list(map(int, stdin.readline().split()))\n\t\tp = []\n\t\tfor (x, y) in zip(arr, arr2):\n\t\t\tp.append((x, y))\n\t\tp.sort(key=lambda x: x[0])\n\t\tP = (1, 1)\n\t\tdist = 0\n\t\tfor (x, y) in p:\n\t\t\tif x == 1:\n\t\t\t\tcontinue\n\t\t\tif y - P[1] == x - P[0]:\n\t\t\t\tif (P[0] + P[1]) % 2 == 0:\n\t\t\t\t\tdist += x - P[0]\n\t\t\t\tP = (x, y)\n\t\t\t\tcontinue\n\t\t\tif P[0] == 1:\n\t\t\t\tP = (2, 1)\n\t\t\tif (P[0] + P[1]) % 2 == 0:\n\t\t\t\tP = (P[0] + 1, P[1])\n\t\t\tP = (P[0] + (y - P[1]), y)\n\t\t\tdist += math.ceil((x - P[0]) / 2)\n\t\t\tP = (x, y)\n\t\tstdout.write(str(dist) + '\\n')\nmain()\n", "cas = int(input())\nwhile cas:\n\tcas -= 1\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\ta = list(zip(r, c))\n\ta.sort()\n\tnow = 0\n\tpre = 0\n\tpr = 1\n\tpz = 0\n\tans = 0\n\tfor i in range(n):\n\t\ttmp = a[i]\n\t\tnow = tmp[0] - tmp[1]\n\t\tzu = now // 2\n\t\tif pre == now and now % 2 == 0:\n\t\t\tans += tmp[0] - pr\n\t\tif pre != now and zu != pz:\n\t\t\tans += zu - pz\n\t\tpre = now\n\t\tpr = tmp[0]\n\t\tpz = zu\n\tprint(ans)\n", "def calc_dist(r1, c1, r2, c2):\n\tif r1 - c1 == r2 - c2:\n\t\tif (r1 + c1) % 2 == 1:\n\t\t\treturn 0\n\t\telse:\n\t\t\treturn r2 - r1\n\tr2 -= r1 - 1\n\tc2 -= c1 - 1\n\tif (r1 + c1) % 2 == 0:\n\t\treturn (r2 - c2) // 2\n\telse:\n\t\treturn (r2 - c2 + 1) // 2\nt = int(input())\nfor _ in range(t):\n\tn = int(input())\n\tr = [int(s) for s in input().split(' ')]\n\tc = [int(s) for s in input().split(' ')]\n\tpts = list(zip(r, c))\n\tpts.sort()\n\tcur_r = 1\n\tcur_c = 1\n\tans = 0\n\tfor (nxt_r, nxt_c) in pts:\n\t\tans += calc_dist(cur_r, cur_c, nxt_r, nxt_c)\n\t\tcur_r = nxt_r\n\t\tcur_c = nxt_c\n\tprint(ans)\n", "t = int(input())\nfor _ in range(t):\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\tl = [(r[i], c[i]) for i in range(n)]\n\tl.sort()\n\t(x, y) = (1, 1)\n\tans = 0\n\tfor (nx, ny) in l:\n\t\tneed = ny - y\n\t\tdif = nx - x\n\t\tif (x + y) % 2 == 0:\n\t\t\tif dif == need:\n\t\t\t\tans += need\n\t\t\telse:\n\t\t\t\tleft = dif - need\n\t\t\t\tans += left // 2\n\t\telif dif == need:\n\t\t\tans += 0\n\t\telse:\n\t\t\tleft = dif - need\n\t\t\tans += (left + 1) // 2\n\t\tx = nx\n\t\ty = ny\n\tprint(ans)\n", "import sys\ninput = sys.stdin.readline\n\ndef calcDist(r1, c1, r2, c2):\n\tif r1 - c1 == r2 - c2:\n\t\treturn r2 - r1 if (r1 + c1) % 2 == 0 else 0\n\tr2 -= r1 - 1\n\tc2 -= c1 - 1\n\treturn (r2 - c2) // 2 if (r1 + c1) % 2 == 0 else (r2 - c2 + 1) // 2\nfor _ in range(int(input())):\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\tp = [(x, y) for (x, y) in zip(r, c)]\n\tp.sort()\n\tans = 0\n\t(lastX, lastY) = (1, 1)\n\tfor (x, y) in p:\n\t\tans += calcDist(lastX, lastY, x, y)\n\t\t(lastX, lastY) = (x, y)\n\tprint(ans)\n", "def dist(r1, c1, r2, c2):\n\tif r1 - c1 == r2 - c2:\n\t\tif (r1 + c1) % 2 == 0:\n\t\t\trez = r2 - r1\n\t\telse:\n\t\t\trez = 0\n\telse:\n\t\tr2 = r2 - (r1 - 1)\n\t\tc2 = c2 - (c1 - 1)\n\t\tif (r1 + c1) % 2 == 0:\n\t\t\trez = (r2 - c2) // 2\n\t\telse:\n\t\t\trez = (r2 - c2 + 1) // 2\n\treturn rez\nt = int(input())\nfor j in range(t):\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\td = sorted(zip(r, c))\n\tans = 0\n\t(r0, c0) = (1, 1)\n\tfor (r, c) in d:\n\t\tans += dist(r0, c0, r, c)\n\t\t(r0, c0) = (r, c)\n\tprint(ans)\n", "def helper(a, b):\n\tif a == b:\n\t\treturn 0\n\t(x0, y0) = a\n\t(x1, y1) = b\n\tif (x0 + y0) % 2 == 0:\n\t\tx0 += 1\n\ty0 += x1 - x0\n\tif y1 > y0:\n\t\treturn x1 - x0 + 1\n\telif y1 == y0:\n\t\treturn 0\n\telse:\n\t\treturn (y0 - y1 + 1) // 2\nfor i in range(int(input())):\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\tpool = sorted([[1, 1]] + [[r[i], c[i]] for i in range(n)])\n\tprint(sum([helper(pool[i - 1], pool[i]) for i in range(1, n + 1)]))\n", "import sys\ninput = sys.stdin.readline\nt = int(input())\nfor _ in range(t):\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\tres = []\n\tfor i in range(n):\n\t\tres.append([r[i], c[i]])\n\tres.sort()\n\t(lastp, lastq) = (1, 1)\n\tans = 0\n\ti = 0\n\twhile i < n:\n\t\t(currp, currq) = (res[i][0], res[i][1])\n\t\tif currp - currq == lastp - lastq:\n\t\t\tif (currp - currq) % 2 == 0:\n\t\t\t\tans += currp - lastp\n\t\telif currp - currq >= lastp - lastq:\n\t\t\tans += (currp - currq) // 2 - (lastp - lastq) // 2\n\t\t(lastp, lastq) = (currp, currq)\n\t\ti += 1\n\tprint(ans)\n", "import sys\nimport io\nimport math\nimport collections\nimport decimal\nimport itertools\nimport bisect\nimport heapq\n\ndef input():\n\treturn sys.stdin.readline()[:-1]\n\ndef solve(N, R, C):\n\tL = [(R[i], C[i]) for i in range(N)]\n\tL.sort()\n\tif L[0] != (1, 1):\n\t\tL = [(1, 1)] + L\n\tn = 0\n\tfor i in range(len(L) - 1):\n\t\t(r1, c1) = L[i]\n\t\t(r2, c2) = L[i + 1]\n\t\tif (r1 - c1) // 2 == (r2 - c2) // 2:\n\t\t\tif (r2 - c2) % 2 == 0:\n\t\t\t\tn += r2 - r1\n\t\telse:\n\t\t\tn += abs((r1 - c1) // 2 - (r2 - c2) // 2)\n\treturn n\n\ndef main():\n\tT0 = int(input())\n\tfor _ in range(T0):\n\t\tN = int(input())\n\t\tR = list(map(int, input().split()))\n\t\tC = list(map(int, input().split()))\n\t\tans = solve(N, R, C)\n\t\tprint(ans)\nmain()\n", "import sys\ninput = sys.stdin.readline\nt = int(input().strip())\nfor __ in range(t):\n\tn = int(input().strip())\n\trarr = [int(val) for val in input().strip().split(' ')]\n\tcarr = [int(val) for val in input().strip().split(' ')]\n\tarr = [(0, 1, 1)] + [(r - c, r, c) for (r, c) in zip(rarr, carr)]\n\tarr.sort()\n\tres = 0\n\tfor i in range(n):\n\t\tdelta = arr[i + 1][0] - arr[i][0]\n\t\tif delta % 2:\n\t\t\tif arr[i][0] % 2:\n\t\t\t\tres += delta // 2 + 1\n\t\t\telse:\n\t\t\t\tres += delta // 2\n\t\telif delta == 0 and arr[i][0] % 2 == 0:\n\t\t\tres += arr[i + 1][1] - arr[i][1]\n\t\telse:\n\t\t\tres += delta // 2\n\tprint(res)\n", "for _ in range(int(input())):\n\tn = int(input())\n\t(*rows,) = map(int, input().split())\n\t(*cols,) = map(int, input().split())\n\tpoints = sorted(range(n), key=lambda i: rows[i])\n\tprev_row = 0\n\tprev_col = 0\n\tans = 0\n\tfor point in points:\n\t\tprev_diag = prev_row - prev_col\n\t\trow = rows[point] - 1\n\t\tcol = cols[point] - 1\n\t\tcur_diag = row - col\n\t\tif cur_diag == prev_diag and cur_diag & 1 == 0:\n\t\t\tans += row - prev_row\n\t\tif prev_diag & 1 == 0:\n\t\t\tprev_diag += 1\n\t\tans += (cur_diag - prev_diag + 1) // 2\n\t\t(prev_row, prev_col) = (row, col)\n\tprint(ans)\n", "import sys\ninput = sys.stdin.readline\n\ndef main():\n\tt = int(input())\n\tfor _ in range(t):\n\t\tn = int(input())\n\t\tr = list(map(int, input().split()))\n\t\tc = list(map(int, input().split()))\n\t\tpoints = [(r[i], c[i]) for i in range(n)]\n\t\tpoints.sort(key=lambda x: x[0])\n\t\tif points[0] != (1, 1):\n\t\t\tpoints = [(1, 1)] + points\n\t\t\tn += 1\n\t\tcost = 0\n\t\tfor i in range(n - 1):\n\t\t\tprev = points[i]\n\t\t\tnow = points[i + 1]\n\t\t\tprev_diff = prev[0] - prev[1]\n\t\t\tnow_diff = now[0] - now[1]\n\t\t\tif prev_diff == now_diff:\n\t\t\t\tif prev_diff % 2 == 0:\n\t\t\t\t\tcost += now[0] - prev[0]\n\t\t\t\telse:\n\t\t\t\t\tpass\n\t\t\telif prev_diff + 1 == now_diff and prev_diff % 2 == 0:\n\t\t\t\tpass\n\t\t\telse:\n\t\t\t\tcost += now_diff // 2 - prev_diff // 2\n\t\tprint(cost)\nmain()\n", "import os, sys\nfrom io import BytesIO, IOBase\nfrom types import GeneratorType\nfrom bisect import bisect_left, bisect_right\nfrom collections import defaultdict as dd, deque as dq, Counter as dc\nimport math, string\nimport heapq as h, time\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\timport os\n\t\tself.os = os\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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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\tself.os.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')\n\ndef getInt():\n\treturn int(input())\n\ndef getStrs():\n\treturn input().split()\n\ndef getInts():\n\treturn list(map(int, input().split()))\n\ndef getStr():\n\treturn input()\n\ndef listStr():\n\treturn list(input())\n\ndef getMat(n):\n\treturn [getInts() for _ in range(n)]\n\ndef getBin():\n\treturn list(map(int, list(input())))\n\ndef isInt(s):\n\treturn '0' <= s[0] <= '9'\n\ndef ceil_(a, b):\n\treturn a // b + (a % b > 0)\nMOD = 10 ** 9 + 7\n\ndef solve():\n\tN = getInt()\n\tR = [1] + getInts()\n\tC = [1] + getInts()\n\tP = list(zip(R, C))\n\tP.sort()\n\tans = 0\n\tflag = False\n\tfor (r, c) in P:\n\t\tif flag:\n\t\t\tif r - c == r0 - c0:\n\t\t\t\tif (r - c) % 2 == 0:\n\t\t\t\t\tans += r - r0\n\t\t\telse:\n\t\t\t\tdelta = r - c - (r0 - c0)\n\t\t\t\tif (r0 - c0) % 2 == 0:\n\t\t\t\t\tans += delta // 2\n\t\t\t\telse:\n\t\t\t\t\tans += ceil_(delta, 2)\n\t\t(r0, c0) = (r, c)\n\t\tflag = True\n\treturn ans\nfor _ in range(getInt()):\n\tprint(solve())\n", "import io\nimport os\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\n\ndef solve():\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\tpoints = []\n\tfor (ri, ci) in zip(r, c):\n\t\tri -= 1\n\t\tci -= 1\n\t\tpoints.append((ri - ci, ci))\n\tpoints.sort()\n\ttotal = 0\n\t(r, c) = (0, 0)\n\tfor (rp, cp) in points:\n\t\ttotal += (rp - r) // 2\n\t\tif rp % 2 == 0 and r % 2 == 1:\n\t\t\ttotal += 1\n\t\tif rp == r and rp % 2 == 0:\n\t\t\ttotal += cp - c\n\t\t(r, c) = (rp, cp)\n\tprint(total)\nt = int(input())\nfor _ in range(t):\n\tsolve()\n", "from bisect import bisect_left, bisect_right\nfrom collections import defaultdict\nimport sys\n\ndef input():\n\treturn sys.stdin.readline().rstrip()\nalphabet = [chr(ord('a') + i) for i in range(26)]\n\ndef slv():\n\tn = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tA = [(u, v) for (u, v) in zip(a, b)] + [(1, 1)]\n\tA.sort(key=lambda x: x[0])\n\tans = 0\n\tfor i in range(n):\n\t\t(px, py) = A[i]\n\t\t(qx, qy) = A[i + 1]\n\t\tqx -= px\n\t\tqy -= py\n\t\t(X, Y) = (qx - qy, qy)\n\t\tif (px + py) % 2 != 0:\n\t\t\tans += (X + 1) // 2\n\t\telif X == 0:\n\t\t\tans += Y\n\t\telse:\n\t\t\tans += X // 2\n\tprint(ans)\n\treturn\n\ndef main():\n\tt = int(input())\n\tfor i in range(t):\n\t\tslv()\n\treturn\nmain()\n", "t = int(input())\nfor i in range(t):\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\tnode = list()\n\tnode.append((1, 1))\n\tfor i in range(n):\n\t\tnode.append((r[i], c[i]))\n\tnode.sort()\n\tresult = 0\n\tfor i in range(n):\n\t\t(r, c) = node[i]\n\t\t(n_r, n_c) = node[i + 1]\n\t\tcond = r - c == n_r - n_c and (r - c) % 2 == 0\n\t\tresult += int((n_r - n_c) / 2) - int((r - c) / 2) + (n_r - r) * int(cond)\n\tprint(result)\n", "def test(n, p):\n\tp.sort()\n\tcost = 0\n\tprevd = 0\n\tprevr = 1\n\tprevc = 1\n\tfor i in range(n):\n\t\t(r, c) = p[i]\n\t\td = r - c\n\t\tif prevd == d:\n\t\t\tif d % 2:\n\t\t\t\tcost += 0\n\t\t\telse:\n\t\t\t\tcost += r - prevr\n\t\telse:\n\t\t\tcost += d // 2 - prevd // 2\n\t\tprevr = r\n\t\tprevd = d\n\treturn cost\nfor kT in range(int(input())):\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\tp = [(r[i], c[i]) for i in range(n)]\n\tprint(test(n, p))\n", "def value(sr, sc, tr, tc):\n\tr = tr - sr + 1\n\tc = tc - sc + 1\n\tif r == c:\n\t\treturn (c - 1) * int((sr + sc) % 2 == 0)\n\tif r > c:\n\t\treturn (r - c + (sr + sc) % 2) // 2\n\telse:\n\t\treturn -1\nfor _ in range(int(input())):\n\tn = int(input())\n\tr = [int(i) for i in input().split(' ')]\n\tc = [int(i) for i in input().split(' ')]\n\tT = []\n\tfor i in range(n):\n\t\tT.append((r[i], c[i]))\n\tT = sorted(T)\n\tv = value(1, 1, T[0][0], T[0][1])\n\tfor i in range(1, n):\n\t\tv += value(T[i - 1][0], T[i - 1][1], T[i][0], T[i][1])\n\tprint(v)\n", "def some_random_function():\n\tx = 10\n\tx *= 100\n\ti_dont_know = x\n\twhy_am_i_writing_this = x * x\n\tprint(i_dont_know)\n\tprint(why_am_i_writing_this)\n\ndef some_random_function5():\n\tx = 10\n\tx *= 100\n\ti_dont_know = x\n\twhy_am_i_writing_this = x * x\n\tprint(i_dont_know)\n\tprint(why_am_i_writing_this)\nimport os, sys\nfrom io import BytesIO, IOBase\n\ndef main():\n\tfor _ in range(int(input())):\n\t\tn = int(input())\n\t\tr = list(map(int, input().split()))\n\t\tc = list(map(int, input().split()))\n\t\tans = 0\n\t\torde = sorted(range(n), key=lambda xx: r[xx])\n\t\torde.sort(key=lambda xx: r[xx] - c[xx])\n\t\tcurr = 0\n\t\tpoi = (1, 1)\n\t\tfor i in orde:\n\t\t\tz = r[i] - c[i]\n\t\t\tif z == curr:\n\t\t\t\tif not curr & 1:\n\t\t\t\t\tans += abs(r[i] - poi[0])\n\t\t\telse:\n\t\t\t\tans += (z - curr + (curr & 1)) // 2\n\t\t\tpoi = (r[i], c[i])\n\t\t\tcurr = z\n\t\tprint(ans)\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')\n\ndef some_random_function1():\n\tx = 10\n\tx *= 100\n\ti_dont_know = x\n\twhy_am_i_writing_this = x * x\n\tprint(i_dont_know)\n\tprint(why_am_i_writing_this)\n\ndef some_random_function2():\n\tx = 10\n\tx *= 100\n\ti_dont_know = x\n\twhy_am_i_writing_this = x * x\n\tprint(i_dont_know)\n\tprint(why_am_i_writing_this)\n\ndef some_random_function3():\n\tx = 10\n\tx *= 100\n\ti_dont_know = x\n\twhy_am_i_writing_this = x * x\n\tprint(i_dont_know)\n\tprint(why_am_i_writing_this)\n\ndef some_random_function4():\n\tx = 10\n\tx *= 100\n\ti_dont_know = x\n\twhy_am_i_writing_this = x * x\n\tprint(i_dont_know)\n\tprint(why_am_i_writing_this)\n\ndef some_random_function6():\n\tx = 10\n\tx *= 100\n\ti_dont_know = x\n\twhy_am_i_writing_this = x * x\n\tprint(i_dont_know)\n\tprint(why_am_i_writing_this)\n\ndef some_random_function7():\n\tx = 10\n\tx *= 100\n\ti_dont_know = x\n\twhy_am_i_writing_this = x * x\n\tprint(i_dont_know)\n\tprint(why_am_i_writing_this)\n\ndef some_random_function8():\n\tx = 10\n\tx *= 100\n\ti_dont_know = x\n\twhy_am_i_writing_this = x * x\n\tprint(i_dont_know)\n\tprint(why_am_i_writing_this)\nmain()\n", "P = lambda : map(int, input().split())\nfor _ in range(*P()):\n\t(n,) = P()\n\td = [(1, 1)] + sorted(zip(P(), P()))\n\ta = 0\n\tfor i in range(n):\n\t\t(r, c) = d[i]\n\t\tv = r - c\n\t\t(R, C) = d[i + 1]\n\t\ta += (R - C) // 2 - v // 2 + (R - r) * (v & 1 < 1 and v == R - C)\n\tprint(a)\n", "import math\nimport random\nimport heapq, bisect\nimport sys\nfrom collections import deque, defaultdict\nfrom fractions import Fraction\nimport sys\nfrom collections import defaultdict\nmod = 10 ** 9 + 7\nmod1 = 998244353\nimport 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')\n\nclass TreeNode:\n\n\tdef __init__(self, k, v):\n\t\tself.key = k\n\t\tself.value = v\n\t\tself.left = None\n\t\tself.right = None\n\t\tself.parent = None\n\t\tself.height = 1\n\t\tself.num_left = 1\n\t\tself.num_total = 1\n\nclass AvlTree:\n\n\tdef __init__(self):\n\t\tself._tree = None\n\n\tdef add(self, k, v):\n\t\tif not self._tree:\n\t\t\tself._tree = TreeNode(k, v)\n\t\t\treturn\n\t\tnode = self._add(k, v)\n\t\tif node:\n\t\t\tself._rebalance(node)\n\n\tdef _add(self, k, v):\n\t\tnode = self._tree\n\t\twhile node:\n\t\t\tif k < node.key:\n\t\t\t\tif node.left:\n\t\t\t\t\tnode = node.left\n\t\t\t\telse:\n\t\t\t\t\tnode.left = TreeNode(k, v)\n\t\t\t\t\tnode.left.parent = node\n\t\t\t\t\treturn node.left\n\t\t\telif node.key < k:\n\t\t\t\tif node.right:\n\t\t\t\t\tnode = node.right\n\t\t\t\telse:\n\t\t\t\t\tnode.right = TreeNode(k, v)\n\t\t\t\t\tnode.right.parent = node\n\t\t\t\t\treturn node.right\n\t\t\telse:\n\t\t\t\tnode.value = v\n\t\t\t\treturn\n\n\t@staticmethod\n\tdef get_height(x):\n\t\treturn x.height if x else 0\n\n\t@staticmethod\n\tdef get_num_total(x):\n\t\treturn x.num_total if x else 0\n\n\tdef _rebalance(self, node):\n\t\tn = node\n\t\twhile n:\n\t\t\tlh = self.get_height(n.left)\n\t\t\trh = self.get_height(n.right)\n\t\t\tn.height = max(lh, rh) + 1\n\t\t\tbalance_factor = lh - rh\n\t\t\tn.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)\n\t\t\tn.num_left = 1 + self.get_num_total(n.left)\n\t\t\tif balance_factor > 1:\n\t\t\t\tif self.get_height(n.left.left) < self.get_height(n.left.right):\n\t\t\t\t\tself._rotate_left(n.left)\n\t\t\t\tself._rotate_right(n)\n\t\t\telif balance_factor < -1:\n\t\t\t\tif self.get_height(n.right.right) < self.get_height(n.right.left):\n\t\t\t\t\tself._rotate_right(n.right)\n\t\t\t\tself._rotate_left(n)\n\t\t\telse:\n\t\t\t\tn = n.parent\n\n\tdef _remove_one(self, node):\n\t\treplacement = node.left or node.right\n\t\tif node.parent:\n\t\t\tif AvlTree._is_left(node):\n\t\t\t\tnode.parent.left = replacement\n\t\t\telse:\n\t\t\t\tnode.parent.right = replacement\n\t\t\treplacement.parent = node.parent\n\t\t\tnode.parent = None\n\t\telse:\n\t\t\tself._tree = replacement\n\t\t\treplacement.parent = None\n\t\tnode.left = None\n\t\tnode.right = None\n\t\tnode.parent = None\n\t\tself._rebalance(replacement)\n\n\tdef _remove_leaf(self, node):\n\t\tif node.parent:\n\t\t\tif AvlTree._is_left(node):\n\t\t\t\tnode.parent.left = None\n\t\t\telse:\n\t\t\t\tnode.parent.right = None\n\t\t\tself._rebalance(node.parent)\n\t\telse:\n\t\t\tself._tree = None\n\t\tnode.parent = None\n\t\tnode.left = None\n\t\tnode.right = None\n\n\tdef remove(self, k):\n\t\tnode = self._get_node(k)\n\t\tif not node:\n\t\t\treturn\n\t\tif AvlTree._is_leaf(node):\n\t\t\tself._remove_leaf(node)\n\t\t\treturn\n\t\tif node.left and node.right:\n\t\t\tnxt = AvlTree._get_next(node)\n\t\t\tnode.key = nxt.key\n\t\t\tnode.value = nxt.value\n\t\t\tif self._is_leaf(nxt):\n\t\t\t\tself._remove_leaf(nxt)\n\t\t\telse:\n\t\t\t\tself._remove_one(nxt)\n\t\t\tself._rebalance(node)\n\t\telse:\n\t\t\tself._remove_one(node)\n\n\tdef get(self, k):\n\t\tnode = self._get_node(k)\n\t\treturn node.value if node else -1\n\n\tdef _get_node(self, k):\n\t\tif not self._tree:\n\t\t\treturn None\n\t\tnode = self._tree\n\t\twhile node:\n\t\t\tif k < node.key:\n\t\t\t\tnode = node.left\n\t\t\telif node.key < k:\n\t\t\t\tnode = node.right\n\t\t\telse:\n\t\t\t\treturn node\n\t\treturn None\n\n\tdef get_at(self, pos):\n\t\tx = pos + 1\n\t\tnode = self._tree\n\t\twhile node:\n\t\t\tif x < node.num_left:\n\t\t\t\tnode = node.left\n\t\t\telif node.num_left < x:\n\t\t\t\tx -= node.num_left\n\t\t\t\tnode = node.right\n\t\t\telse:\n\t\t\t\treturn (node.key, node.value)\n\t\traise IndexError('Out of ranges')\n\n\t@staticmethod\n\tdef _is_left(node):\n\t\treturn node.parent.left and node.parent.left == node\n\n\t@staticmethod\n\tdef _is_leaf(node):\n\t\treturn node.left is None and node.right is None\n\n\tdef _rotate_right(self, node):\n\t\tif not node.parent:\n\t\t\tself._tree = node.left\n\t\t\tnode.left.parent = None\n\t\telif AvlTree._is_left(node):\n\t\t\tnode.parent.left = node.left\n\t\t\tnode.left.parent = node.parent\n\t\telse:\n\t\t\tnode.parent.right = node.left\n\t\t\tnode.left.parent = node.parent\n\t\tbk = node.left.right\n\t\tnode.left.right = node\n\t\tnode.parent = node.left\n\t\tnode.left = bk\n\t\tif bk:\n\t\t\tbk.parent = node\n\t\tnode.height = max(self.get_height(node.left), self.get_height(node.right)) + 1\n\t\tnode.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)\n\t\tnode.num_left = 1 + self.get_num_total(node.left)\n\n\tdef _rotate_left(self, node):\n\t\tif not node.parent:\n\t\t\tself._tree = node.right\n\t\t\tnode.right.parent = None\n\t\telif AvlTree._is_left(node):\n\t\t\tnode.parent.left = node.right\n\t\t\tnode.right.parent = node.parent\n\t\telse:\n\t\t\tnode.parent.right = node.right\n\t\t\tnode.right.parent = node.parent\n\t\tbk = node.right.left\n\t\tnode.right.left = node\n\t\tnode.parent = node.right\n\t\tnode.right = bk\n\t\tif bk:\n\t\t\tbk.parent = node\n\t\tnode.height = max(self.get_height(node.left), self.get_height(node.right)) + 1\n\t\tnode.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)\n\t\tnode.num_left = 1 + self.get_num_total(node.left)\n\n\t@staticmethod\n\tdef _get_next(node):\n\t\tif not node.right:\n\t\t\treturn node.parent\n\t\tn = node.right\n\t\twhile n.left:\n\t\t\tn = n.left\n\t\treturn n\n\nclass SegmentTree2:\n\n\tdef __init__(self, data, default=3000006, func=lambda a, b: min(a, b)):\n\t\tself._default = default\n\t\tself._func = func\n\t\tself._len = len(data)\n\t\tself._size = _size = 1 << (self._len - 1).bit_length()\n\t\tself.data = [default] * (2 * _size)\n\t\tself.data[_size:_size + self._len] = data\n\t\tfor i in reversed(range(_size)):\n\t\t\tself.data[i] = func(self.data[i + i], self.data[i + i + 1])\n\n\tdef __delitem__(self, idx):\n\t\tself[idx] = self._default\n\n\tdef __getitem__(self, idx):\n\t\treturn self.data[idx + self._size]\n\n\tdef __setitem__(self, idx, value):\n\t\tidx += self._size\n\t\tself.data[idx] = value\n\t\tidx >>= 1\n\t\twhile idx:\n\t\t\tself.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])\n\t\t\tidx >>= 1\n\n\tdef __len__(self):\n\t\treturn self._len\n\n\tdef query(self, start, stop):\n\t\tif start == stop:\n\t\t\treturn self.__getitem__(start)\n\t\tstop += 1\n\t\tstart += self._size\n\t\tstop += self._size\n\t\tres = self._default\n\t\twhile start < stop:\n\t\t\tif start & 1:\n\t\t\t\tres = self._func(res, self.data[start])\n\t\t\t\tstart += 1\n\t\t\tif stop & 1:\n\t\t\t\tstop -= 1\n\t\t\t\tres = self._func(res, self.data[stop])\n\t\t\tstart >>= 1\n\t\t\tstop >>= 1\n\t\treturn res\n\n\tdef __repr__(self):\n\t\treturn 'SegmentTree({0})'.format(self.data)\n\nclass SegmentTree1:\n\n\tdef __init__(self, data, default=10 ** 10, func=lambda a, b: min(a, b)):\n\t\tself._default = default\n\t\tself._func = func\n\t\tself._len = len(data)\n\t\tself._size = _size = 1 << (self._len - 1).bit_length()\n\t\tself.data = [default] * (2 * _size)\n\t\tself.data[_size:_size + self._len] = data\n\t\tfor i in reversed(range(_size)):\n\t\t\tself.data[i] = func(self.data[i + i], self.data[i + i + 1])\n\n\tdef __delitem__(self, idx):\n\t\tself[idx] = self._default\n\n\tdef __getitem__(self, idx):\n\t\treturn self.data[idx + self._size]\n\n\tdef __setitem__(self, idx, value):\n\t\tidx += self._size\n\t\tself.data[idx] = value\n\t\tidx >>= 1\n\t\twhile idx:\n\t\t\tself.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])\n\t\t\tidx >>= 1\n\n\tdef __len__(self):\n\t\treturn self._len\n\n\tdef query(self, start, stop):\n\t\tif start == stop:\n\t\t\treturn self.__getitem__(start)\n\t\tstop += 1\n\t\tstart += self._size\n\t\tstop += self._size\n\t\tres = self._default\n\t\twhile start < stop:\n\t\t\tif start & 1:\n\t\t\t\tres = self._func(res, self.data[start])\n\t\t\t\tstart += 1\n\t\t\tif stop & 1:\n\t\t\t\tstop -= 1\n\t\t\t\tres = self._func(res, self.data[stop])\n\t\t\tstart >>= 1\n\t\t\tstop >>= 1\n\t\treturn res\n\n\tdef __repr__(self):\n\t\treturn 'SegmentTree({0})'.format(self.data)\n\nclass SegmentTree:\n\n\tdef __init__(self, data, default=0, func=lambda a, b: a + b):\n\t\tself._default = default\n\t\tself._func = func\n\t\tself._len = len(data)\n\t\tself._size = _size = 1 << (self._len - 1).bit_length()\n\t\tself.data = [default] * (2 * _size)\n\t\tself.data[_size:_size + self._len] = data\n\t\tfor i in reversed(range(_size)):\n\t\t\tself.data[i] = func(self.data[i + i], self.data[i + i + 1])\n\n\tdef __delitem__(self, idx):\n\t\tself[idx] = self._default\n\n\tdef __getitem__(self, idx):\n\t\treturn self.data[idx + self._size]\n\n\tdef __setitem__(self, idx, value):\n\t\tidx += self._size\n\t\tself.data[idx] = value\n\t\tidx >>= 1\n\t\twhile idx:\n\t\t\tself.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])\n\t\t\tidx >>= 1\n\n\tdef __len__(self):\n\t\treturn self._len\n\n\tdef query(self, start, stop):\n\t\tif start == stop:\n\t\t\treturn self.__getitem__(start)\n\t\tstop += 1\n\t\tstart += self._size\n\t\tstop += self._size\n\t\tres = self._default\n\t\twhile start < stop:\n\t\t\tif start & 1:\n\t\t\t\tres = self._func(res, self.data[start])\n\t\t\t\tstart += 1\n\t\t\tif stop & 1:\n\t\t\t\tstop -= 1\n\t\t\t\tres = self._func(res, self.data[stop])\n\t\t\tstart >>= 1\n\t\t\tstop >>= 1\n\t\treturn res\n\n\tdef __repr__(self):\n\t\treturn 'SegmentTree({0})'.format(self.data)\n\nclass Factorial:\n\n\tdef __init__(self, MOD):\n\t\tself.MOD = MOD\n\t\tself.factorials = [1, 1]\n\t\tself.invModulos = [0, 1]\n\t\tself.invFactorial_ = [1, 1]\n\n\tdef calc(self, n):\n\t\tif n <= -1:\n\t\t\tprint('Invalid argument to calculate n!')\n\t\t\tprint('n must be non-negative value. But the argument was ' + str(n))\n\t\t\texit()\n\t\tif n < len(self.factorials):\n\t\t\treturn self.factorials[n]\n\t\tnextArr = [0] * (n + 1 - len(self.factorials))\n\t\tinitialI = len(self.factorials)\n\t\tprev = self.factorials[-1]\n\t\tm = self.MOD\n\t\tfor i in range(initialI, n + 1):\n\t\t\tprev = nextArr[i - initialI] = prev * i % m\n\t\tself.factorials += nextArr\n\t\treturn self.factorials[n]\n\n\tdef inv(self, n):\n\t\tif n <= -1:\n\t\t\tprint('Invalid argument to calculate n^(-1)')\n\t\t\tprint('n must be non-negative value. But the argument was ' + str(n))\n\t\t\texit()\n\t\tp = self.MOD\n\t\tpi = n % p\n\t\tif pi < len(self.invModulos):\n\t\t\treturn self.invModulos[pi]\n\t\tnextArr = [0] * (n + 1 - len(self.invModulos))\n\t\tinitialI = len(self.invModulos)\n\t\tfor i in range(initialI, min(p, n + 1)):\n\t\t\tnext = -self.invModulos[p % i] * (p // i) % p\n\t\t\tself.invModulos.append(next)\n\t\treturn self.invModulos[pi]\n\n\tdef invFactorial(self, n):\n\t\tif n <= -1:\n\t\t\tprint('Invalid argument to calculate (n^(-1))!')\n\t\t\tprint('n must be non-negative value. But the argument was ' + str(n))\n\t\t\texit()\n\t\tif n < len(self.invFactorial_):\n\t\t\treturn self.invFactorial_[n]\n\t\tself.inv(n)\n\t\tnextArr = [0] * (n + 1 - len(self.invFactorial_))\n\t\tinitialI = len(self.invFactorial_)\n\t\tprev = self.invFactorial_[-1]\n\t\tp = self.MOD\n\t\tfor i in range(initialI, n + 1):\n\t\t\tprev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p\n\t\tself.invFactorial_ += nextArr\n\t\treturn self.invFactorial_[n]\n\nclass Combination:\n\n\tdef __init__(self, MOD):\n\t\tself.MOD = MOD\n\t\tself.factorial = Factorial(MOD)\n\n\tdef ncr(self, n, k):\n\t\tif k < 0 or n < k:\n\t\t\treturn 0\n\t\tk = min(k, n - k)\n\t\tf = self.factorial\n\t\treturn f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD\n\ndef powm(a, n, m):\n\tif a == 1 or n == 0:\n\t\treturn 1\n\tif n % 2 == 0:\n\t\ts = powm(a, n // 2, m)\n\t\treturn s * s % m\n\telse:\n\t\treturn a * powm(a, n - 1, m) % m\n\ndef sort_list(list1, list2):\n\tzipped_pairs = zip(list2, list1)\n\tz = [x for (_, x) in sorted(zipped_pairs)]\n\treturn z\n\ndef product(l):\n\tpor = 1\n\tfor i in range(len(l)):\n\t\tpor *= l[i]\n\treturn por\n\ndef binarySearchCount(arr, n, key):\n\tleft = 0\n\tright = n - 1\n\tcount = 0\n\twhile left <= right:\n\t\tmid = int((right + left) / 2)\n\t\tif arr[mid] <= key:\n\t\t\tcount = mid + 1\n\t\t\tleft = mid + 1\n\t\telse:\n\t\t\tright = mid - 1\n\treturn count\n\ndef countdig(n):\n\tc = 0\n\twhile n > 0:\n\t\tn //= 10\n\t\tc += 1\n\treturn c\n\ndef binary(x, length):\n\ty = bin(x)[2:]\n\treturn y if len(y) >= length else '0' * (length - len(y)) + y\n\ndef countGreater(arr, n, k):\n\tl = 0\n\tr = n - 1\n\tleftGreater = n\n\twhile l <= r:\n\t\tm = int(l + (r - l) / 2)\n\t\tif arr[m] > k:\n\t\t\tleftGreater = m\n\t\t\tr = m - 1\n\t\telse:\n\t\t\tl = m + 1\n\treturn n - leftGreater\n\nclass TrieNode:\n\n\tdef __init__(self):\n\t\tself.children = [None] * 26\n\t\tself.isEndOfWord = False\n\nclass Trie:\n\n\tdef __init__(self):\n\t\tself.root = self.getNode()\n\n\tdef getNode(self):\n\t\treturn TrieNode()\n\n\tdef _charToIndex(self, ch):\n\t\treturn ord(ch) - ord('a')\n\n\tdef insert(self, key):\n\t\tpCrawl = self.root\n\t\tlength = len(key)\n\t\tfor level in range(length):\n\t\t\tindex = self._charToIndex(key[level])\n\t\t\tif not pCrawl.children[index]:\n\t\t\t\tpCrawl.children[index] = self.getNode()\n\t\t\tpCrawl = pCrawl.children[index]\n\t\tpCrawl.isEndOfWord = True\n\n\tdef search(self, key):\n\t\tpCrawl = self.root\n\t\tlength = len(key)\n\t\tfor level in range(length):\n\t\t\tindex = self._charToIndex(key[level])\n\t\t\tif not pCrawl.children[index]:\n\t\t\t\treturn False\n\t\t\tpCrawl = pCrawl.children[index]\n\t\treturn pCrawl != None and pCrawl.isEndOfWord\n\nclass Node:\n\n\tdef __init__(self, data):\n\t\tself.data = data\n\t\tself.count = 0\n\t\tself.left = None\n\t\tself.right = None\n\nclass BinaryTrie:\n\n\tdef __init__(self):\n\t\tself.root = Node(0)\n\n\tdef insert(self, pre_xor, t):\n\t\tself.temp = self.root\n\t\tfor i in range(31, -1, -1):\n\t\t\tval = pre_xor & 1 << i\n\t\t\tif val:\n\t\t\t\tif not self.temp.right:\n\t\t\t\t\tself.temp.right = Node(0)\n\t\t\t\tself.temp = self.temp.right\n\t\t\t\tself.temp.count += t\n\t\t\tif not val:\n\t\t\t\tif not self.temp.left:\n\t\t\t\t\tself.temp.left = Node(0)\n\t\t\t\tself.temp = self.temp.left\n\t\t\t\tself.temp.count += t\n\t\tself.temp.data = pre_xor\n\n\tdef query(self, p, l):\n\t\tans = 0\n\t\tself.temp = self.root\n\t\tfor i in range(31, -1, -1):\n\t\t\tval = p & 1 << i\n\t\t\tval1 = l & 1 << i\n\t\t\tif val1 == 0:\n\t\t\t\tif val == 0:\n\t\t\t\t\tif self.temp.left and self.temp.left.count > 0:\n\t\t\t\t\t\tself.temp = self.temp.left\n\t\t\t\t\telse:\n\t\t\t\t\t\treturn ans\n\t\t\t\telif self.temp.right and self.temp.right.count > 0:\n\t\t\t\t\tself.temp = self.temp.right\n\t\t\t\telse:\n\t\t\t\t\treturn ans\n\t\t\telif val != 0:\n\t\t\t\tif self.temp.right:\n\t\t\t\t\tans += self.temp.right.count\n\t\t\t\tif self.temp.left and self.temp.left.count > 0:\n\t\t\t\t\tself.temp = self.temp.left\n\t\t\t\telse:\n\t\t\t\t\treturn ans\n\t\t\telse:\n\t\t\t\tif self.temp.left:\n\t\t\t\t\tans += self.temp.left.count\n\t\t\t\tif self.temp.right and self.temp.right.count > 0:\n\t\t\t\t\tself.temp = self.temp.right\n\t\t\t\telse:\n\t\t\t\t\treturn ans\n\t\treturn ans\nfor ik in range(int(input())):\n\tn = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tb = sort_list(b, a)\n\ta.sort()\n\tlast = 1\n\tlast1 = 1\n\tans = 0\n\tfor i in range(n):\n\t\t(r1, c1) = (a[i], b[i])\n\t\tif (r1 + c1) % 2 == 0 and r1 - last == c1 - last1:\n\t\t\tans += r1 - last\n\t\telse:\n\t\t\tif (last + last1) % 2 == 0:\n\t\t\t\tlast += 1\n\t\t\tlast += c1 - last1\n\t\t\tans += int(math.ceil((r1 - last) / 2))\n\t\tlast = r1\n\t\tlast1 = c1\n\tprint(ans)\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nfrom collections import deque, Counter, defaultdict\nfrom heapq import heapify, heappush, heappop\n\ndef solve(Y, X, N):\n\tpoints = list(zip(Y, X))\n\tpoints.sort()\n\tres = 0\n\ty1 = x1 = 1\n\tfor (y2, x2) in points:\n\t\tif y1 - x1 == y2 - x2:\n\t\t\tif (y1 + x1) % 2 == 0:\n\t\t\t\tres += y2 - y1\n\t\telse:\n\t\t\ty3 = y2 - y1 + 1\n\t\t\tx3 = x2 - x1 + 1\n\t\t\tif (y1 + x1) % 2 == 0:\n\t\t\t\tres += (y3 - x3) // 2\n\t\t\telse:\n\t\t\t\tres += (y3 - x3 + 1) // 2\n\t\t(y1, x1) = (y2, x2)\n\treturn res\n\ndef main():\n\tfor _ in range(inInt()):\n\t\tN = inInt()\n\t\tY = inLst()\n\t\tX = inLst()\n\t\toutInt(solve(Y, X, 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')\ninInt = lambda : int(input())\ninLst = lambda : list(map(int, input().split()))\ninStr = lambda : list(input())\ninVar = lambda : map(int, input().split())\noutInt = lambda n: sys.stdout.write(str(n) + '\\n')\noutLst = lambda lst: sys.stdout.write(' '.join(map(str, lst)) + '\\n')\noutStr = lambda s: sys.stdout.write(''.join(s) + '\\n')\nmain()\n", "for _ in range(int(input())):\n\tn = int(input())\n\trow = map(int, input().split())\n\tcol = map(int, input().split())\n\tpos = [(1, 1)]\n\tfor (r, c) in zip(row, col):\n\t\tpos.append((r, c))\n\tpos.sort()\n\tcost = 0\n\tfor i in range(n):\n\t\t(r1, c1) = pos[i]\n\t\t(r2, c2) = pos[i + 1]\n\t\tif r1 - c1 == r2 - c2:\n\t\t\tif (r1 - c1) % 2 == 0:\n\t\t\t\tcost += r2 - r1\n\t\telse:\n\t\t\td = abs(r1 - c1 - (r2 - c2))\n\t\t\tcost += d // 2\n\t\t\tif d % 2 == 1 and (r1 - c1) % 2 == 1:\n\t\t\t\tcost += 1\n\tprint(cost)\n", "def seal(a, b):\n\treturn (a + b - 1) // b\nfor _ in range(int(input())):\n\tn = int(input())\n\tr = [int(x) for x in input().split()]\n\tc = [int(x) for x in input().split()]\n\tarr = [[r[i], c[i]] for i in range(n)]\n\tarr.sort()\n\tans = 0\n\tif arr[0] != [1, 1]:\n\t\tarr.insert(0, [1, 1])\n\tn = len(arr)\n\tprev = [1, 1]\n\tfor i in range(1, n):\n\t\tcurr = arr[i]\n\t\tif sum(prev) & 1:\n\t\t\tif curr[0] - prev[0] & 1:\n\t\t\t\tans += seal(curr[0] - prev[0], 2) - seal(curr[1] - prev[1], 2)\n\t\t\telse:\n\t\t\t\tans += seal(curr[0] - prev[0], 2) - (curr[1] - prev[1] >> 1)\n\t\telif curr[0] - prev[0] == curr[1] - prev[1]:\n\t\t\tans += curr[0] - prev[0]\n\t\telif curr[0] - prev[0] & 1:\n\t\t\tans += (curr[0] - prev[0] >> 1) - (curr[1] - prev[1] >> 1)\n\t\telse:\n\t\t\tans += (curr[0] - prev[0] >> 1) - seal(curr[1] - prev[1], 2)\n\t\tprev = curr\n\tprint(ans)\n", "t = int(input())\nfor i in range(t):\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\tz = []\n\tz.append((1, 1))\n\tfor i in range(n):\n\t\tz.append((r[i], c[i]))\n\tz.sort()\n\tnode = z\n\tres = 0\n\tfor i in range(n):\n\t\t(r, c) = node[i]\n\t\t(nr, nc) = node[i + 1]\n\t\tres += (nr - nc) // 2 - (r - c) // 2 + (nr - r if r - c == nr - nc and (r - c) % 2 == 0 else 0)\n\tprint(res)\n", "from collections import defaultdict, OrderedDict, Counter\nfrom sys import stdin, stdout\nfrom bisect import bisect_left, bisect_right\nfrom queue import Queue, PriorityQueue\nfrom heapq import *\nfrom statistics import *\nfrom math import *\nimport fractions\nimport copy\nfrom copy import deepcopy\nimport sys\nimport io\nsys.setrecursionlimit(10000)\nimport math\nimport os\nimport bisect\nimport collections\nmod = pow(10, 9) + 7\nimport random\nfrom random import *\nfrom time import time\n\ndef ncr(n, r, p=mod):\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 normalncr(n, r):\n\tr = min(r, n - r)\n\tcount = 1\n\tfor i in range(n - r, n + 1):\n\t\tcount *= i\n\tfor i in range(1, r + 1):\n\t\tcount //= i\n\treturn count\ninf = float('inf')\nadj = defaultdict(set)\nvisited = defaultdict(int)\n\ndef addedge(a, b):\n\tadj[a].add(b)\n\tadj[b].add(a)\n\ndef bfs(v):\n\tq = Queue()\n\tq.put(v)\n\tvisited[v] = 1\n\twhile q.qsize() > 0:\n\t\ts = q.get_nowait()\n\t\tprint(s)\n\t\tfor i in adj[s]:\n\t\t\tif visited[i] == 0:\n\t\t\t\tq.put(i)\n\t\t\t\tvisited[i] = 1\n\ndef dfs(v, visited):\n\tif visited[v] == 1:\n\t\treturn\n\tvisited[v] = 1\n\tprint(v)\n\tfor i in adj[v]:\n\t\tdfs(i, visited)\n\ndef reverse_bisect_right(a, x, lo=0, hi=None):\n\tif lo < 0:\n\t\traise ValueError('lo must be non-negative')\n\tif hi is None:\n\t\thi = len(a)\n\twhile lo < hi:\n\t\tmid = (lo + hi) // 2\n\t\tif x > a[mid]:\n\t\t\thi = mid\n\t\telse:\n\t\t\tlo = mid + 1\n\treturn lo\n\ndef reverse_bisect_left(a, x, lo=0, hi=None):\n\tif lo < 0:\n\t\traise ValueError('lo must be non-negative')\n\tif hi is None:\n\t\thi = len(a)\n\twhile lo < hi:\n\t\tmid = (lo + hi) // 2\n\t\tif x >= a[mid]:\n\t\t\thi = mid\n\t\telse:\n\t\t\tlo = mid + 1\n\treturn lo\n\ndef get_list():\n\treturn list(map(int, input().split()))\n\ndef get_str_list_in_int():\n\treturn [int(i) for i in list(input())]\n\ndef get_str_list():\n\treturn list(input())\n\ndef get_map():\n\treturn map(int, input().split())\n\ndef input_int():\n\treturn int(input())\n\ndef matrix(a, b):\n\treturn [[0 for i in range(b)] for j in range(a)]\n\ndef swap(a, b):\n\treturn (b, a)\n\ndef find_gcd(l):\n\ta = l[0]\n\tfor i in range(len(l)):\n\t\ta = gcd(a, l[i])\n\treturn a\n\ndef is_prime(n):\n\tsqrta = int(sqrt(n))\n\tfor i in range(2, sqrta + 1):\n\t\tif n % i == 0:\n\t\t\treturn 0\n\treturn 1\n\ndef prime_factors(n):\n\twhile n % 2 == 0:\n\t\treturn [2] + prime_factors(n // 2)\n\tsqrta = int(sqrt(n))\n\tfor i in range(3, sqrta + 1, 2):\n\t\tif n % i == 0:\n\t\t\treturn [i] + prime_factors(n // i)\n\treturn [n]\n\ndef p(a):\n\tif type(a) == str:\n\t\tprint(a + '\\n')\n\telse:\n\t\tprint(str(a) + '\\n')\n\ndef ps(a):\n\tif type(a) == str:\n\t\tprint(a)\n\telse:\n\t\tprint(str(a))\n\ndef kth_no_not_div_by_n(n, k):\n\treturn k + (k - 1) // (n - 1)\n\ndef forward_array(l):\n\tn = len(l)\n\tstack = []\n\tforward = [0] * n\n\tfor i in range(len(l) - 1, -1, -1):\n\t\twhile len(stack) and l[stack[-1]] < l[i]:\n\t\t\tstack.pop()\n\t\tif len(stack) == 0:\n\t\t\tforward[i] = len(l)\n\t\telse:\n\t\t\tforward[i] = stack[-1]\n\t\tstack.append(i)\n\treturn forward\n\ndef backward_array(l):\n\tn = len(l)\n\tstack = []\n\tbackward = [0] * n\n\tfor i in range(len(l)):\n\t\twhile len(stack) and l[stack[-1]] < l[i]:\n\t\t\tstack.pop()\n\t\tif len(stack) == 0:\n\t\t\tbackward[i] = -1\n\t\telse:\n\t\t\tbackward[i] = stack[-1]\n\t\tstack.append(i)\n\treturn backward\nnc = 'NO'\nyc = 'YES'\nns = 'No'\nys = 'Yes'\n\ndef add(m, theta):\n\tcounter = 0\n\tres = [i for i in m]\n\tfor i in range(len(m)):\n\t\tif m[i] == 0:\n\t\t\tres[i] = theta[counter]\n\t\t\tcounter += 1\n\treturn res\nt = int(input())\nfor i in range(t):\n\tn = int(input())\n\ta = get_list()\n\tb = get_list()\n\tl = [[a[i], b[i]] for i in range(n)]\n\tl.sort()\n\tcurr_r = 1\n\tcurr_c = 1\n\tcurr_diff = 0\n\tcost = 0\n\tfor i in range(n):\n\t\t(a, b) = l[i]\n\t\tdiff = a - b\n\t\tif diff == curr_diff:\n\t\t\tif (curr_r + curr_c) % 2 == 0:\n\t\t\t\tcost += abs(a - curr_r)\n\t\t\telse:\n\t\t\t\tpass\n\t\telif (curr_r + curr_c) % 2 == 0:\n\t\t\tcost += abs(diff - curr_diff) // 2\n\t\telse:\n\t\t\tcost += ceil(abs(diff - curr_diff) / 2)\n\t\tcurr_r = a\n\t\tcurr_c = b\n\t\tcurr_diff = diff\n\tprint(cost)\n", "import copy, math, random, re, sys, time\n\ndef input_int():\n\treturn int(input())\n\ndef input_int_list():\n\treturn list(map(int, input().split()))\n\ndef input_str():\n\treturn input()\n\ndef input_str_list():\n\treturn input().split()\n\ndef min_cost(init, fin):\n\tif init == fin:\n\t\treturn 0\n\t(r1, c1) = init\n\t(r2, c2) = fin\n\teven = (r1 + c1) % 2 == 0\n\tdr = r2 - r1\n\tdc = c2 - c1\n\tdiag = dc\n\tvert = dr - dc\n\tcost_diag = 0\n\tif even and dr == dc:\n\t\tcost_diag = diag\n\tcost_vert = 0\n\tif even:\n\t\tcost_vert = math.floor(vert / 2)\n\telse:\n\t\tcost_vert = math.ceil(vert / 2)\n\treturn cost_diag + cost_vert\nt = input_int()\nfor idx in range(1, t + 1):\n\tn = input_int()\n\tr = input_int_list()\n\tc = input_int_list()\n\tpoints = [(1, 1)] + [(r[i], c[i]) for i in range(n)]\n\tpoints.sort(key=lambda x: x[0])\n\tcost = 0\n\tfor i in range(len(points) - 1):\n\t\tcost += min_cost(points[i], points[i + 1])\n\tprint(cost)\n", "def main():\n\tt = int(input())\n\tallans = []\n\tfor _ in range(t):\n\t\tn = int(input())\n\t\tr = [1] + readIntArr()\n\t\tc = [1] + readIntArr()\n\t\trc = list(zip(r, c))\n\t\trc.sort(key=lambda x: x[0])\n\t\tans = 0\n\t\tfor i in range(len(rc) - 1):\n\t\t\t(ii1, jj1) = rc[i]\n\t\t\t(ii2, jj2) = rc[i + 1]\n\t\t\tif ii1 == ii2:\n\t\t\t\tcontinue\n\t\t\tk = ii2 - ii1\n\t\t\tif (ii1 + jj1) % 2 == 0:\n\t\t\t\texpectedjj2 = jj1 + k - 1\n\t\t\telse:\n\t\t\t\texpectedjj2 = jj1 + k\n\t\t\tif jj2 > expectedjj2:\n\t\t\t\tassert expectedjj2 + 1 == jj2\n\t\t\t\tans += ii2 - ii1\n\t\t\telse:\n\t\t\t\tans += (1 + expectedjj2 - jj2) // 2\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 queryInteractive(x, y):\n\tprint('? {} {}'.format(x, y))\n\tsys.stdout.flush()\n\treturn int(input())\n\ndef answerInteractive(ans):\n\tprint('! {}'.format(ans))\n\tsys.stdout.flush()\ninf = float('inf')\nMOD = 10 ** 9 + 7\nfor _aa in range(1):\n\tmain()\n", "import sys\ninput = sys.stdin.buffer.readline\nfor _ in range(int(input())):\n\tn = int(input())\n\tp = [(1, 1)] + sorted(list(zip(map(int, input().split()), map(int, input().split()))))\n\tcost = 0\n\tfor i in range(n):\n\t\tback = p[i + 1][0] - p[i][0] - (p[i + 1][1] - p[i][1])\n\t\tif back == 0:\n\t\t\tcost += (1 - sum(p[i]) % 2) * (p[i + 1][0] - p[i][0])\n\t\telse:\n\t\t\tback -= 1 - sum(p[i]) % 2\n\t\t\tcost += (back + 1) // 2\n\tprint(cost)\n", "from collections import defaultdict, deque, Counter\nfrom heapq import heapify, heappop, heappush\nimport math\nfrom copy import deepcopy\nfrom itertools import combinations, permutations, product\nfrom bisect import bisect_left, bisect_right\nimport sys\n\ndef input():\n\treturn sys.stdin.readline().rstrip()\n\ndef getN():\n\treturn int(input())\n\ndef getNM():\n\treturn map(int, input().split())\n\ndef getList():\n\treturn list(map(int, input().split()))\n\ndef getArray(intn):\n\treturn [int(input()) for i in range(intn)]\nmod = 10 ** 9 + 7\nMOD = 998244353\nINF = float('inf')\neps = 10 ** (-10)\ndx = [1, 0, -1, 0]\ndy = [0, 1, 0, -1]\nT = getN()\nfor _ in range(T):\n\tN = getN()\n\tR = [1] + getList()\n\tC = [1] + getList()\n\tP = [[r, c] for (r, c) in zip(R, C)]\n\tP.sort()\n\tans = 0\n\tfor i in range(N):\n\t\tif P[i][0] - P[i][1] == P[i + 1][0] - P[i + 1][1] and (P[i][0] - P[i][1]) % 2 == 0:\n\t\t\tans += P[i + 1][1] - P[i][1]\n\t\t\tcontinue\n\t\tg_a = (P[i][0] - P[i][1]) // 2\n\t\tg_b = (P[i + 1][0] - P[i + 1][1]) // 2\n\t\tans += g_b - g_a\n\tprint(ans)\n", "import sys\nsys.setrecursionlimit(10 ** 7)\ninput = sys.stdin.readline\nf_inf = float('inf')\nMOD = 10 ** 9 + 7\n\ndef solve():\n\tn = int(input())\n\tR = list(map(int, input().split()))\n\tC = list(map(int, input().split()))\n\tpoints = [(r, c) for (r, c) in zip(R, C)]\n\tpoints.sort()\n\tres = 0\n\tpr = pc = 1\n\tfor (r, c) in points:\n\t\tif r - c == pr - pc:\n\t\t\tif (r + c) % 2 == 0:\n\t\t\t\tres += r - pr\n\t\telse:\n\t\t\tif pc != c:\n\t\t\t\tpr += c - pc\n\t\t\t\tpc = c\n\t\t\tif (pr + pc) % 2 == 0:\n\t\t\t\tres += (r - pr) // 2\n\t\t\telse:\n\t\t\t\tres += (r - pr + 1) // 2\n\t\t(pr, pc) = (r, c)\n\tprint(res)\nt = int(input())\nfor _ in range(t):\n\tsolve()\n", "import heapq\nimport sys\ninput = sys.stdin.readline\nt = int(input())\nfor _ in range(t):\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\th = []\n\tfor i in range(n):\n\t\theapq.heappush(h, (r[i], c[i]))\n\t(nowx, nowy) = (1, 1)\n\tans = 0\n\twhile h:\n\t\t(x, y) = heapq.heappop(h)\n\t\tif nowx - nowy == x - y:\n\t\t\tif not (x - y) % 2:\n\t\t\t\tans += x - nowx\n\t\telif nowx - nowy < x - y:\n\t\t\tans += (x - y) // 2 - (nowx - nowy) // 2\n\t\t(nowx, nowy) = (x, y)\n\tprint(ans)\n", "import sys\nmax_int = 2147483648\nmin_int = -max_int\n\ndef calc(r0, c0, r1, c1):\n\td0 = r0 - c0\n\td1 = r1 - c1\n\tif r0 == r1 and c0 == c1:\n\t\treturn 0\n\tif d0 == d1:\n\t\tif d0 % 2:\n\t\t\treturn 0\n\t\telse:\n\t\t\treturn r1 - r0\n\treturn (d1 - d0) // 2 + (1 if d0 % 2 and (not d1 % 2) else 0)\nt = int(input())\nfor _t in range(t):\n\tn = int(sys.stdin.readline())\n\tr = list(map(int, sys.stdin.readline().split()))\n\tc = list(map(int, sys.stdin.readline().split()))\n\tl = []\n\tfor (rr, cc) in zip(r, c):\n\t\tl.append((rr, cc))\n\tl.sort()\n\tprevr = 1\n\tprevc = 1\n\tout = 0\n\tfor (rr, cc) in l:\n\t\tans = calc(prevr, prevc, rr, cc)\n\t\tout += ans\n\t\tprevr = rr\n\t\tprevc = cc\n\tprint(out)\n", "for _ in range(int(input())):\n\tinput()\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\ta = sorted(((x, x + 1 - y) for (x, y) in zip(r, c)))\n\tif a[0] != (1, 1):\n\t\ta = [(1, 1)] + a\n\tans = 0\n\tfor ((x, y), (nx, ny)) in zip(a, a[1:]):\n\t\tassert x < nx and y <= ny and (ny - y <= nx - x)\n\t\tif y == ny and y % 2:\n\t\t\tans += nx - x\n\t\telse:\n\t\t\tans += (ny + 1) // 2 - (y + 1) // 2\n\tprint(ans, sep='\\n')\n", "T = int(input())\nfor t in range(T):\n\tn = int(input())\n\trs = [int(ea) for ea in input().split(' ')]\n\tcs = [int(ea) for ea in input().split(' ')]\n\tpoints = []\n\tfor i in range(n):\n\t\tpoints.append((rs[i], cs[i]))\n\tpoints.sort()\n\tif points[0] != (1, 1):\n\t\tpoints.insert(0, (1, 1))\n\tprev = 0\n\tprevR = 1\n\tcost = 0\n\tfor (r, c) in points[1:]:\n\t\tcur = r - c\n\t\tif cur == prev and cur % 2 == 0:\n\t\t\tcost += r - prevR\n\t\telse:\n\t\t\tdiff = cur - prev\n\t\t\tcost += diff // 2\n\t\t\tif diff % 2 == 1 and prev % 2 == 1:\n\t\t\t\tcost += 1\n\t\tprev = cur\n\t\tprevR = r\n\tprint(cost)\n", "def get_input():\n\tl = [int(e) for e in input().split()]\n\treturn l\n\ndef band(p):\n\td = p[0] - p[1]\n\treturn d // 2\n\ndef cost_path(p1, p2):\n\tb1 = band(p2)\n\tb2 = band(p1)\n\tif b1 > b2:\n\t\treturn b1 - b2\n\telif p1[0] - p1[1] == p2[0] - p2[1]:\n\t\tif (p1[0] - p1[1]) % 2:\n\t\t\treturn 0\n\t\telse:\n\t\t\treturn p2[1] - p1[1]\n\telse:\n\t\treturn 0\n\ndef main(n, r, c):\n\tps = [(ri, ci) for (ri, ci) in zip(r, c)]\n\tps.append((1, 1))\n\tps.sort()\n\tc = 0\n\tfor i in range(n):\n\t\tc += cost_path(ps[i], ps[i + 1])\n\tprint(c)\nt = get_input()[0]\nfor _ in range(t):\n\tn = get_input()[0]\n\tr = get_input()\n\tc = get_input()\n\tmain(n, r, c)\n", "import sys\n\ndef input():\n\treturn sys.stdin.buffer.readline().rstrip()\n\ndef inputa():\n\treturn list(map(int, input().split()))\n\ndef out(var):\n\tsys.stdout.write(str(var) + '\\n')\n\ndef outa(*var):\n\tsys.stdout.write(' '.join(map(str, var)) + '\\n')\n\ndef setup():\n\timport os\n\tdir_path = os.path.dirname(os.path.realpath(__file__))\n\tsys.stdin = open(os.path.join(dir_path, 'input.txt'), 'r')\n\tsys.stdout = open(os.path.join(dir_path, 'output.txt'), 'w')\nfor _ in range(int(input())):\n\tn = int(input())\n\trows = inputa()\n\tcols = inputa()\n\tarr = [(1, 1)] + sorted([(rows[i], cols[i]) for i in range(n)])\n\tcost = 0\n\tfor i in range(1, n + 1):\n\t\t(r0, c0) = arr[i - 1]\n\t\t(r1, c1) = arr[i]\n\t\tif r1 - c1 == r0 - c0:\n\t\t\tif (r1 - c1) % 2 == 0:\n\t\t\t\tcost += r1 - r0\n\t\t\tcontinue\n\t\tdiff = r1 - c1 - (r0 - c0)\n\t\tif (r0 - c0) % 2 == 0:\n\t\t\tcost += diff // 2\n\t\telse:\n\t\t\tcost += (diff + 1) // 2\n\tout(cost)\n", "import sys\nfor _ in range(int(input())):\n\tn = int(input())\n\tf = lambda : map(int, sys.stdin.readline().split())\n\tnode = [(1, 1)] + sorted(zip(f(), f()))\n\tres = 0\n\tfor i in range(n):\n\t\t(r, c) = node[i]\n\t\t(nr, nc) = node[i + 1]\n\t\tres += (nr - nc) // 2 - (r - c) // 2 + (nr - r if r - c == nr - nc and (r - c) % 2 == 0 else 0)\n\tprint(res)\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\tBUFSIZE = 8192\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, self.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, self.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')\n\ndef read_int_list():\n\treturn list(map(int, input().split()))\n\ndef read_int_tuple():\n\treturn tuple(map(int, input().split()))\n\ndef read_int():\n\treturn int(input())\nt = read_int()\nfor _ in range(t):\n\tn = read_int()\n\tr = read_int_list()\n\tc = read_int_list()\n\tpoints = []\n\tfor (ri, ci) in zip(r, c):\n\t\tri -= 1\n\t\tci -= 1\n\t\tpoints.append((ri - ci, ci))\n\tpoints.sort()\n\ttotal = 0\n\t(r, c) = (0, 0)\n\tfor (rp, cp) in points:\n\t\ttotal += (rp - r) // 2\n\t\tif rp % 2 == 0 and r % 2 == 1:\n\t\t\ttotal += 1\n\t\tif rp == r and rp % 2 == 0:\n\t\t\ttotal += cp - c\n\t\t(r, c) = (rp, cp)\n\tprint(total)\n", "def main():\n\tt = int(input())\n\tfor _ in range(t):\n\t\tn = int(input())\n\t\tr = list(map(int, input().split()))\n\t\tc = list(map(int, input().split()))\n\t\trc = []\n\t\tfor i in range(n):\n\t\t\trc.append((r[i], r[i] - c[i] + 1))\n\t\trc.sort(key=lambda x: x[0])\n\t\tpos = (1, 1)\n\t\ttotal = 0\n\t\tfor i in range(n):\n\t\t\tnxt = rc[i]\n\t\t\tif nxt[0] == 1:\n\t\t\t\tcontinue\n\t\t\tdy = nxt[0] - pos[0]\n\t\t\tif pos[1] == nxt[1]:\n\t\t\t\tif pos[1] % 2:\n\t\t\t\t\ttotal += dy\n\t\t\telse:\n\t\t\t\tdx = nxt[1] - pos[1]\n\t\t\t\tif dx % 2:\n\t\t\t\t\tif pos[1] % 2 == 0:\n\t\t\t\t\t\ttotal += 1\n\t\t\t\t\tdx -= 1\n\t\t\t\ttotal += dx // 2\n\t\t\tpos = nxt\n\t\tprint(total)\nmain()\n", "from os import path\nimport sys, time\nmod = int(1000000000.0 + 7)\nfrom math import ceil, floor, gcd, log, log2, factorial, sqrt\nfrom collections import defaultdict, Counter, OrderedDict, deque\nfrom itertools import combinations, permutations\nfrom bisect import *\nfrom functools import reduce\nfrom operator import mul\nmaxx = float('inf')\nI = lambda : int(sys.stdin.buffer.readline())\nlint = lambda : [int(x) for x in sys.stdin.buffer.readline().split()]\nS = lambda : sys.stdin.readline().strip('\\n')\ngrid = lambda r: [lint() for i in range(r)]\nlocalsys = 0\nstart_time = time.time()\nnCr = lambda n, r: reduce(mul, range(n - r + 1, n + 1), 1) // factorial(r)\n\ndef ceill(n, x):\n\treturn (n + x - 1) // x\nT = 1\n\ndef make_set(v):\n\tparent[v] = v\n\ndef find_set(v):\n\tif v == parent[v]:\n\t\treturn v\n\treturn find_set(parent[v])\n\ndef union_sets(a, b):\n\ta = find_set(a)\n\tb = find_set(b)\n\tif a != b:\n\t\tparent[b] = a\n\ndef lcs(x, y):\n\t(m, n) = (len(x), len(y))\n\tdp = [[None] * (n + 1) for _ in range(m + 1)]\n\tfor i in range(m + 1):\n\t\tfor j in range(n + 1):\n\t\t\tif i == 0 or j == 0:\n\t\t\t\tdp[i][j] = 0\n\t\t\telif y[j - 1] == x[i - 1]:\n\t\t\t\tdp[i][j] = dp[i - 1][j - 1] + 1\n\t\t\telse:\n\t\t\t\tdp[i][j] = max(dp[i - 1][j], dp[i][j - 1])\n\treturn dp[m][n]\n\ndef solve():\n\tn = I()\n\t(arr, ans) = ([(1, 1)] + sorted(((i, j) for (i, j) in zip(lint(), lint()))), 0)\n\tfor i in range(n):\n\t\tc = arr[i + 1][0] - arr[i][0] - (arr[i + 1][1] - arr[i][1])\n\t\tif not c:\n\t\t\tans += (1 - sum(arr[i]) % 2) * (arr[i + 1][0] - arr[i][0])\n\t\t\tcontinue\n\t\tans += (c - (1 - sum(arr[i]) % 2) + 1) // 2\n\tprint(ans)\n\ndef run():\n\tif path.exists('input.txt'):\n\t\tsys.stdin = open('input.txt', 'r')\n\t\tsys.stdout = open('output.txt', 'w')\nrun()\nT = I() if T else 1\nfor _ in range(T):\n\tsolve()\nif localsys:\n\tprint('\\n\\nTime Elased :', time.time() - start_time, 'seconds')\n", "import math\nfor _ in range(int(input())):\n\tn = int(input())\n\ta = list(map(int, input().split()))\n\tb = list(map(int, input().split()))\n\tc = []\n\tfor i in range(n):\n\t\tc.append((a[i], b[i]))\n\tc.sort()\n\tif c[0] != (1, 1):\n\t\tc.insert(0, (1, 1))\n\t\tn += 1\n\tcost = 0\n\tfor u in range(n - 1):\n\t\t(p, q) = (c[u][0], c[u][1])\n\t\t(r, s) = (c[u + 1][0], c[u + 1][1])\n\t\tif abs(p - q) == abs(r - s):\n\t\t\tif abs(p - q) % 2:\n\t\t\t\tcontinue\n\t\t\telse:\n\t\t\t\tcost += abs(p - r)\n\t\telse:\n\t\t\tx = abs(p - q)\n\t\t\ty = abs(r - s)\n\t\t\tif y % 2:\n\t\t\t\tcost += abs(x - y) // 2\n\t\t\telse:\n\t\t\t\tcost += int(math.ceil(abs(x - y) / 2))\n\tprint(cost)\n", "import sys\ninput = sys.stdin.readline\nfrom operator import itemgetter\nt = int(input())\nfor tests in range(t):\n\tn = int(input())\n\tR = list(map(int, input().split()))\n\tC = list(map(int, input().split()))\n\tX = []\n\tfor i in range(n):\n\t\tX.append((R[i], C[i]))\n\tX.sort(key=itemgetter(0))\n\tif X[0][0] != 1:\n\t\tX = [(1, 1)] + X\n\tANS = 0\n\tfor i in range(len(X) - 1):\n\t\t(nowx, nowy) = X[i]\n\t\t(nexx, nexy) = X[i + 1]\n\t\tif (nowx - nowy) % 2 == 0:\n\t\t\tif nowx - nowy == nexx - nexy:\n\t\t\t\tANS += nexx - nowx\n\t\t\telse:\n\t\t\t\tANS += (nexx - nexy - (nowx - nowy)) // 2\n\t\telse:\n\t\t\tANS += (nexx - nexy - (nowx - nowy) + 1) // 2\n\tprint(ANS)\n", "import io\nimport os\nfrom collections import Counter, defaultdict, deque\n\ndef solve(N, R, C):\n\tfor (r, c) in zip(R, C):\n\t\tif r == c == 1:\n\t\t\tbreak\n\telse:\n\t\tR.append(1)\n\t\tC.append(1)\n\t\tN += 1\n\torder = sorted(list(range(N)), key=lambda i: R[i])\n\tans = 0\n\tfor (i, j) in zip(order, order[1:]):\n\t\tr1 = R[i]\n\t\tc1 = C[i]\n\t\tr2 = R[j]\n\t\tc2 = C[j]\n\t\td1 = r1 - c1\n\t\td2 = r2 - c2\n\t\tcost = 0\n\t\tif d1 % 2 == 0 and d1 == d2:\n\t\t\tcost = r2 - r1\n\t\telse:\n\t\t\tcost = d2 // 2 - d1 // 2\n\t\tans += cost\n\treturn ans\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\nTC = int(input())\nfor tc in range(1, TC + 1):\n\t(N,) = [int(x) for x in input().split()]\n\tR = [int(x) for x in input().split()]\n\tC = [int(x) for x in input().split()]\n\tans = solve(N, R, C)\n\tprint(ans)\n", "import sys, math\n\ndef getCount(p1, p2):\n\tif p2[1] - p1[1] == p2[0] - p1[0]:\n\t\tif (p1[0] + p1[1]) % 2 == 0:\n\t\t\treturn p2[0] - p1[0]\n\t\telse:\n\t\t\treturn 0\n\tif (p1[0] + p1[1]) % 2 == 0:\n\t\tp1[0] += 1\n\treturn math.ceil((p2[0] - p1[0] - p2[1] + p1[1]) / 2)\nt = int(sys.stdin.readline())\nfor tt in range(t):\n\tn = int(sys.stdin.readline())\n\tarr1 = list(map(int, sys.stdin.readline().split()))\n\tarr2 = list(map(int, sys.stdin.readline().split()))\n\tarr = sorted(list(zip(arr1, arr2)))\n\tloc = [1, 1]\n\tans = 0\n\tfor i in arr:\n\t\tif list(i) == loc:\n\t\t\tcontinue\n\t\tans += getCount(loc, i)\n\t\t(loc[0], loc[1]) = (i[0], i[1])\n\tprint(ans)\n", "import sys\ninput = sys.stdin.readline\nfrom collections import *\nfor _ in range(int(input())):\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\trc = [(ri, ci) for (ri, ci) in zip(r, c)]\n\trc.sort()\n\tplevel = 0\n\tpr = 1\n\tpc = 1\n\tans = 0\n\tfor (r, c) in rc:\n\t\tlevel = (r - c) // 2\n\t\tans += level - plevel\n\t\tif level == plevel and (pr - pc) % 2 == 0 and ((r - c) % 2 == 0):\n\t\t\tans += r - pr\n\t\tplevel = level\n\t\tpr = r\n\t\tpc = c\n\tprint(ans)\n", "import sys\nfrom sys import stdin\ntt = int(stdin.readline())\nANS = []\nfor loop in range(tt):\n\tn = int(stdin.readline())\n\tr = list(map(int, stdin.readline().split()))\n\tc = list(map(int, stdin.readline().split()))\n\tr.sort()\n\tc.sort()\n\tif not r[0] == c[0] == 1:\n\t\tr.append(1)\n\t\tc.append(1)\n\tdic = {}\n\tmaxl = 0\n\tfor i in range(len(r)):\n\t\tmaxl = max(maxl, r[i] - c[i])\n\t\tif (r[i] + c[i]) % 2 == 0:\n\t\t\tif r[i] - c[i] not in dic:\n\t\t\t\tdic[r[i] - c[i]] = []\n\t\t\tdic[r[i] - c[i]].append(r[i])\n\tans = maxl // 2\n\tfor x in dic:\n\t\tdic[x].sort()\n\t\tans += dic[x][-1] - dic[x][0]\n\tANS.append(ans)\nprint('\\n'.join(map(str, ANS)))\n", "for _ in range(int(input())):\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\tarr = sorted(list(zip(r, c)))\n\tcorrection = (1, 1)\n\tans = 0\n\tcheck = True\n\tfor point in arr:\n\t\t(r, c) = (point[0] - correction[0] + 1, point[1] - correction[1] + 1)\n\t\tdepth = r - 1\n\t\tif r == c:\n\t\t\tif check:\n\t\t\t\tans += depth\n\t\telse:\n\t\t\tif not check:\n\t\t\t\tans += 1\n\t\t\tans += (r - c - int(not check)) // 2\n\t\tcorrection = point\n\t\tif (r + c) % 2 != 0:\n\t\t\tcheck = not check\n\tprint(ans)\n", "from 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\tn = int(input())\n\trr = [1] + [int(a) for a in input().split()]\n\tcc = [1] + [int(a) for a in input().split()]\n\trc = sorted(zip(rr, cc))\n\tres = 0\n\tfor ((r1, c1), (r2, c2)) in zip(rc, rc[1:]):\n\t\tif (r1 + c1) % 2 == 0 and c2 - r2 == c1 - r1:\n\t\t\tres += r2 - r1\n\t\telse:\n\t\t\tif (r1 + c1) % 2 == 0:\n\t\t\t\tr1 += 1\n\t\t\tres += (r2 - c2 - (r1 - c1) + 1) // 2\n\tprint(res)\n\ndef main():\n\tt = int(input())\n\tfor _ in range(t):\n\t\tsolve()\nmain()\n", "import sys\ninput = sys.stdin.readline\nfor _ in range(int(input())):\n\tn = int(input())\n\tr = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\tps = [(r[i], c[i]) for i in range(n)]\n\tps.sort()\n\ty = 1\n\tx = 1\n\tres = 0\n\tfor i in range(n):\n\t\t(u, v) = ps[i]\n\t\tif y == u and x == v:\n\t\t\tcontinue\n\t\tif (y + x) % 2 == 0:\n\t\t\tif y + 1 == u and x + 1 == v:\n\t\t\t\tres += 1\n\t\t\t\t(y, x) = (u, v)\n\t\t\t\tcontinue\n\t\t\ty += 1\n\t\tuv = u - v\n\t\tyx = y - x\n\t\tif uv >= yx:\n\t\t\tres += -((yx - uv) // 2)\n\t\telse:\n\t\t\tres += abs(v - x)\n\t\t(y, x) = (u, v)\n\tprint(res)\n", "import sys\nmod = 998244353\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nfrom _collections import deque\nfrom math import ceil\nfor counter in range(int(input())):\n\tn = int(input())\n\tck = []\n\tfor (i, j) in zip(input().split(), input().split()):\n\t\tck.append([int(i), int(j)])\n\tck.sort()\n\ttot = 0\n\t(r, c) = (1, 1)\n\tfor (i, j) in ck:\n\t\tif r - c == i - j:\n\t\t\tif not (r + c) % 2:\n\t\t\t\ttot += j - c\n\t\telse:\n\t\t\tif not (r + c) % 2:\n\t\t\t\tr += 1\n\t\t\tt = i - r\n\t\t\tjm = c + t\n\t\t\ttot += ceil((jm - j) / 2)\n\t\t(r, c) = (i, j)\n\tprint(tot)\n"]

difficulty: HARD

source: codeforces

raw_problem:
F. Triangular Paths

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Consider an infinite triangle made up of layers. Let's number the layers, starting from one, from the top of the triangle (from top to bottom). The $$$k$$$-th layer of the triangle contains $$$k$$$ points, numbered from left to right. Each point of an infinite triangle is described by a pair of numbers $$$(r, c)$$$ ($$$1 \le c \le r$$$), where $$$r$$$ is the number of the layer, and $$$c$$$ is the number of the point in the layer. From each point $$$(r, c)$$$ there are two directed edges to the points $$$(r+1, c)$$$ and $$$(r+1, c+1)$$$, but only one of the edges is activated. If $$$r + c$$$ is even, then the edge to the point $$$(r+1, c)$$$ is activated, otherwise the edge to the point $$$(r+1, c+1)$$$ is activated. Look at the picture for a better understanding.
  Activated edges are colored in black. Non-activated edges are colored in gray.
From the point $$$(r_1, c_1)$$$ it is possible to reach the point $$$(r_2, c_2)$$$, if there is a path between them only from activated edges. For example, in the picture above, there is a path from $$$(1, 1)$$$ to $$$(3, 2)$$$, but there is no path from $$$(2, 1)$$$ to $$$(1, 1)$$$.

Initially, you are at the point $$$(1, 1)$$$. For each turn, you can:

 Replace activated edge for point $$$(r, c)$$$. That is if the edge to the point $$$(r+1, c)$$$ is activated, then instead of it, the edge to the point $$$(r+1, c+1)$$$ becomes activated, otherwise if the edge to the point $$$(r+1, c+1)$$$, then instead if it, the edge to the point $$$(r+1, c)$$$ becomes activated. This action increases the cost of the path by $$$1$$$;

 Move from the current point to another by following the activated edge. This action does not increase the cost of the path.

You are given a sequence of $$$n$$$ points of an infinite triangle $$$(r_1, c_1), (r_2, c_2), \ldots, (r_n, c_n)$$$. Find the minimum cost path from $$$(1, 1)$$$, passing through all $$$n$$$ points in arbitrary order.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) is the number of test cases. Then $$$t$$$ test cases follow.

Each test case begins with a line containing one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) is the number of points to visit.

The second line contains $$$n$$$ numbers $$$r_1, r_2, \ldots, r_n$$$ ($$$1 \le r_i \le 10^9$$$), where $$$r_i$$$ is the number of the layer in which $$$i$$$-th point is located.

The third line contains $$$n$$$ numbers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le r_i$$$), where $$$c_i$$$ is the number of the $$$i$$$-th point in the $$$r_i$$$ layer.

It is guaranteed that all $$$n$$$ points are distinct.

It is guaranteed that there is always at least one way to traverse all $$$n$$$ points.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output the minimum cost of a path passing through all points in the corresponding test case.

Example

Input

4
3
1 4 2
1 3 1
2
2 4
2 3
2
1 1000000000
1 1000000000
4
3 10 5 8
2 5 2 4

Output

0
1
999999999
2

question:
Consider an infinite triangle made up of layers. Let's number the layers, starting from one, from the top of the triangle (from top to bottom). The $$$k$$$-th layer of the triangle contains $$$k$$$ points, numbered from left to right. Each point of an infinite triangle is described by a pair of numbers $$$(r, c)$$$ ($$$1 \le c \le r$$$), where $$$r$$$ is the number of the layer, and $$$c$$$ is the number of the point in the layer. From each point $$$(r, c)$$$ there are two directed edges to the points $$$(r+1, c)$$$ and $$$(r+1, c+1)$$$, but only one of the edges is activated. If $$$r + c$$$ is even, then the edge to the point $$$(r+1, c)$$$ is activated, otherwise the edge to the point $$$(r+1, c+1)$$$ is activated. Look at the picture for a better understanding.
 ![image](1.png) Activated edges are colored in black. Non-activated edges are colored in gray. From the point $$$(r_1, c_1)$$$ it is possible to reach the point $$$(r_2, c_2)$$$, if there is a path between them only from activated edges. For example, in the picture above, there is a path from $$$(1, 1)$$$ to $$$(3, 2)$$$, but there is no path from $$$(2, 1)$$$ to $$$(1, 1)$$$.
Initially, you are at the point $$$(1, 1)$$$. For each turn, you can:
 -  Replace activated edge for point $$$(r, c)$$$. That is if the edge to the point $$$(r+1, c)$$$ is activated, then instead of it, the edge to the point $$$(r+1, c+1)$$$ becomes activated, otherwise if the edge to the point $$$(r+1, c+1)$$$, then instead if it, the edge to the point $$$(r+1, c)$$$ becomes activated. This action increases the cost of the path by $$$1$$$; -  Move from the current point to another by following the activated edge. This action does not increase the cost of the path. You are given a sequence of $$$n$$$ points of an infinite triangle $$$(r_1, c_1), (r_2, c_2), \ldots, (r_n, c_n)$$$. Find the minimum cost path from $$$(1, 1)$$$, passing through all $$$n$$$ points in arbitrary order.

Input
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) is the number of test cases. Then $$$t$$$ test cases follow.
Each test case begins with a line containing one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) is the number of points to visit.
The second line contains $$$n$$$ numbers $$$r_1, r_2, \ldots, r_n$$$ ($$$1 \le r_i \le 10^9$$$), where $$$r_i$$$ is the number of the layer in which $$$i$$$-th point is located.
The third line contains $$$n$$$ numbers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le r_i$$$), where $$$c_i$$$ is the number of the $$$i$$$-th point in the $$$r_i$$$ layer.
It is guaranteed that all $$$n$$$ points are distinct.
It is guaranteed that there is always at least one way to traverse all $$$n$$$ points.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output
For each test case, output the minimum cost of a path passing through all points in the corresponding test case.

Example
Input
4
3
1 4 2
1 3 1
2
2 4
2 3
2
1 1000000000
1 1000000000
4
3 10 5 8
2 5 2 4

Output
0
1
999999999
2

tags: ['Graph algorithms', 'Shortest paths', 'Constructive algorithms', 'Sorting', 'Mathematics']

skill_types: ['Sorting']

raw_tags: ['math', 'shortest paths', 'graphs', 'sortings', 'constructive algorithms']

data_split: test